Loading...
Please wait, while we are loading the content...
Similar Documents
Outfix-free regular languages and prime outfix-free decomposition (2007).
| Content Provider | CiteSeerX |
|---|---|
| Author | Wood, Derick Han, Yo-Sub |
| Abstract | A string x is an outfix of a string y if there is a string w such that x1wx2 = y and x = x1x2. A set X of strings is outfix-free if no string in X is an outfix of any other string in X. Based on the properties of outfix strings, we develop a polynomial-time algorithm that determines outfix-freeness of regular languages. Note that outfix-free regular languages are always finite. We consider two cases: 1) a language is given as a finite set of strings and 2) a language is given by a finite-state automaton. Furthermore, we investigate the prime outfix-free decomposition of outfixfree regular languages and design a linear-time algorithm that computes prime outfix-free decomposition for outfix-free regular languages. We also demonstrate the uniqueness of prime outfix-free decomposition. |
| File Format | |
| Publisher Date | 2007-01-01 |
| Access Restriction | Open |
| Subject Keyword | Prime Outfix-free Decomposition Polynomial-time Algorithm Outfix-free Regular Language Outfix String Regular Language Finite-state Automaton Finite Set Linear-time Algorithm Outfixfree Regular Language |
| Content Type | Text |
