|
|||||
|
|
Minimal forbidden subwords |
|
| Authors: | Tatjana Petkovi? Miroslav ?iri? |
| Affiliation: | a Academy of Finland and Department of Information Technology, University of Turku, FIN-20014 Turku, Finland b Faculty of Sciences and Mathematics, University of Niš, P.O. Box 224, 18000 Niš, Yugoslavia c Faculty of Economics, University of Niš, P.O. Box 121, 18000 Niš, Yugoslavia |
| Abstract: | Motivated by a study of similar problems stated for factors of words, we study forbidden subwords of a language or a word. A procedure for obtaining the set of all words avoiding a given set of subwords is presented. On the other hand, an algorithm for computing the set of minimal forbidden subwords for a word is given. The case of a two-letter alphabet appears to be particularly interesting and it is considered separately. |
| Keywords: | Subwords Automata Formal languages Combinatorics on words Orders of words |
| 本文献已被 ScienceDirect 等数据库收录！ | |