Paper Info
Title
On Free Inverse Monoid Languages
Abstract
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.
Year
DOI
Venue
1996
10.1051/ita/1996300403491
RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS
Field
DocType
Volume
Inverse,Combinatorics,Automata theory,Algebraic number,Abstract family of languages,Monoid,Operator (computer programming),Cone (formal languages),Free monoid,Mathematics
Journal
30
Issue
Citations 
PageRank 
4
13
1.15
References 
Authors
2
1
Name
Order
Citations
PageRank
Pedro V. Silva114129.42