A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Composition and orbits of language operations: finiteness and upper bounds
Tekijät: Charlier E, Domaratzki M, Harju T, Shallit J
Kustantaja: TAYLOR & FRANCIS LTD
Julkaisuvuosi: 2013
Journal: International Journal of Computer Mathematics
Tietokannassa oleva lehden nimi: INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
Lehden akronyymi: INT J COMPUT MATH
Numero sarjassa: 6
Vuosikerta: 90
Numero: 6
Aloitussivu: 1171
Lopetussivu: 1196
Sivujen määrä: 26
ISSN: 0020-7160
eISSN: 1029-0265
DOI: https://doi.org/10.1080/00207160.2012.681305
Verkko-osoite: http://www.tandfonline.com/toc/gcom20/90/6
Tiivistelmä
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, independent 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.
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, independent 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.
Turun yliopiston Tutkimustietojärjestelmän portaali