Name
Abstract | ||
|---|---|---|
We give a quadratic-time algorithm to compute the set of minimal forbidden words of a factorial regular language. We give a linear-time algorithm to compute the minimal forbidden words of a finite set of words. This extends a previous result given for the case of a single word only.We also give quadratic-time algorithms to check whether a regular language is factorial or anti-factorial. |
Year | Venue | Keywords |
|---|---|---|
2003 | Fundamenta Informaticae - Computing Patterns in Strings | anti-factorial language,formal languages,failure function,linear-time algorithm,factorial lan guage,sofic shift,finite set,factor automaton,quadratic-time algorithm,regular language,symbolic dynamics.,single word,factorial regular language,forbid- den word,previous result,symbolic dynamics,formal language,linear time |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Context-sensitive language,Finite set,Formal language,Nondeterministic finite automaton,Factorial,Pumping lemma for regular languages,Regular language,Regular grammar,Mathematics | Journal | 56 |
Issue | ISSN | Citations |
1-2 | 0169-2968 | 17 |
PageRank | References | Authors |
1.28 | 7 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marie-pierre Béal | 1 | 327 | 35.73 |
| Maxime Crochemore | 2 | 2655 | 281.75 |
| Filippo Mignosi | 3 | 569 | 99.71 |
| Antonio Restivo | 4 | 697 | 107.05 |
| Marinella Sciortino | 5 | 225 | 22.34 |