On free inverse monoid languages

• Type: Article in International Scientific Journal
• Date: 1996

Authors

Pedro V. Silva (Author) FCUP

Journal

Title: RAIRO - Theoretical Informatics and Applications

Vol. 30 No. 4

Pages: 349-378

ISSN: 0988-3754

Publisher: EDP Sciences

Indexing

ISI Web of Knowledge - 17 Citations

ISI Web of Science

Scopus - 19 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-001-FKG

DOI: 10.1051/ita/1996300403491

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