Abstract (EN):
This is a study on the class of FIM(X)-languages and its important subfamily consisting of inverse automata languages (i-languages). Bath algebraic and combinatorial approaches are used to obtain several results concerning closure operators on (X boolean OR X(-1))*-languages, including a classification of FIM(X)-languages by i-languages. In particular, it is proved that the i-closure of a recognizable (X boolean OR X(-1))*-language is at most deterministic context-free. Infinite trees are an essential tool in this process, and they are also helpful in producing counterexamples for other closure problems. Applications to X*-languages are also produced, involving particular classes of codes.
Language:
English
Type (Professor's evaluation):
Scientific
No. of pages:
30