| Title | Constructing finite maximal codes from Schuetzenberger Conjecture |
| Authors | Marcella Anselmo, Dip. Informatica ed Appl. - Universita' degli studi di Salerno |
| Main Fields | 2. automata
8. formal languages |
| Other Main Fields | |
| Abstract + Keywords | Schuetzenberger Conjecture claims that
any finite maximal code
C is factorizing, i.e. SC*P=A* in a non-ambiguous way, for some S,P. Let us suppose that Schuetzenberger Conjecture holds. Two problems arise: the construction of all (S,P) and the construction of C starting from (S,P). Regarding the first problem we consider two families of possible languages S: S prefix-closed and S s.t. S\ {1} is a code. For the second problem we present a method of constructing C from (S,P), that is relied on the construction of right- and left-factors of a language. Results are based on a combinatorial characterization of right- and left- factorizing languages. Keywords: Formal Languages, Non-ambiguous Factorizations, Factorizing Codes |