Article (Scientific journals)
Composition and orbits of language operations: finiteness and upper bounds
Charlier, Emilie; Domaratzki, Michael; Harju, Tero et al.
2013In International Journal of Computer Mathematics, 90 (6), p. 1171-1196
Peer Reviewed verified by ORBi
 

Files


Full Text
charlier-domaratzki-harju.pdf
Author postprint (349.99 kB)
Request a copy

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
formal language; Kleene closure; complement; automaton; orbit
Abstract :
[en] We consider a set of eight natural operations on formal languages (Kleene closure, positive closure, complement, prefix, suffix, factor, subword, and reversal), and compositions of them. If x and y are compositions, we say x is equivalent to y if they have the same effect on all languages L. We prove that the number of equivalence classes of these eight operations is finite. This implies that the orbit of any language L under the elements of the monoid is finite and bounded, independently of L. This generalizes previous results about complement, Kleene closure, and positive closure. We also estimate the number of distinct languages generated by various subsets of these operations.
Disciplines :
Mathematics
Author, co-author :
Charlier, Emilie  ;  University of Waterloo > School of Computer Science
Domaratzki, Michael
Harju, Tero
Shallit, Jeffrey
Language :
English
Title :
Composition and orbits of language operations: finiteness and upper bounds
Publication date :
June 2013
Journal title :
International Journal of Computer Mathematics
ISSN :
0020-7160
Publisher :
Taylor & Francis Ltd
Volume :
90
Issue :
6
Pages :
1171-1196
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 19 June 2012

Statistics


Number of views
115 (20 by ULiège)
Number of downloads
1 (1 by ULiège)

Scopus citations®
 
3
Scopus citations®
without self-citations
2
OpenCitations
 
3
OpenAlex citations
 
4

Bibliography


Similar publications



Contact ORBi