INFIX-FREE REGULAR EXPRESSIONS AND LANGUAGES
Authors:
- 1 April 2006
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 17 (02) , 379-393
Abstract
We study infix-free regular languages. We observe the structural properties of finite-state automata for infix-free languages and develop a polynomial-time algorithm to determine infix-freeness of a regular language using state-pair graphs. We consider two cases: 1) A language is specified by a nondeterministic finite-state automaton and 2) a language is specified by a regular expression. Furthermore, we examine the prime infix-free decomposition of infix-free regular languages and design an algorithm for the infix-free primality test of an infix-free regular language. Moreover, we show that we can compute the prime infix-free decomposition in polynomial time. We also demonstrate that the prime infix-free decomposition is not unique.Keywords
This publication has 9 references indexed in Scilit:
- THE GENERALIZATION OF GENERALIZED AUTOMATA: EXPRESSION AUTOMATAInternational Journal of Foundations of Computer Science, 2005
- LINEAR-TIME PRIME DECOMPOSITION OF REGULAR PREFIX CODESInternational Journal of Foundations of Computer Science, 2003
- Automata and forbidden wordsInformation Processing Letters, 1998
- Structure of 3-infix-outfix maximal codesTheoretical Computer Science, 1997
- On the use of regular expressions for searching textACM Transactions on Programming Languages and Systems, 1997
- Codes11997
- Outfix and infix codes and related classes of languagesJournal of Computer and System Sciences, 1991
- n-Prefix–suffix languages∗International Journal of Computer Mathematics, 1989
- Programming Techniques: Regular expression search algorithmCommunications of the ACM, 1968