Reference : Composition and orbits of language operations: finiteness and upper bounds
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/125557
Composition and orbits of language operations: finiteness and upper bounds
English
Charlier, Emilie mailto [University of Waterloo > School of Computer Science > > >]
Domaratzki, Michael [> >]
Harju, Tero [> >]
Shallit, Jeffrey [> >]
Jun-2013
International Journal of Computer Mathematics
Taylor & Francis Ltd
90
6
1171-1196
Yes (verified by ORBi)
International
0020-7160
[en] formal language ; Kleene closure ; complement ; automaton ; orbit
[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.
Researchers
http://hdl.handle.net/2268/125557
10.1080/00207160.2012.681305

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Restricted access
charlier-domaratzki-harju.pdfAuthor postprint341.78 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.