On Shuffling a Word with its Letter-to-Letter Substitution

• Autorzy: Halava Vesa , Harju Tero , Sahla Esa

Identyfikatory

DOI

10.3233/FI-2020-1954

• Języki publikacji: EN

Abstrakty

EN

Denote by ш the operation of interleaving, or shuffling, of words. We prove that, given a regular language R and a letter-to-letter morphism φ , it is undecidable whether or not there exists a word ω such that ω ш φ (ω ) ∩ R ≠ Ø.

Słowa kluczowe

EN

vocabulary; language

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 175, nr 1-4
• Strony: 201--206
• Opis fizyczny: Bibliogr. 8 poz., rys.

Twórcy

autor

Halava Vesa

• Complex Systems Research Group, Department of Mathematics and Statistics, University of Turku, Finland

autor

Harju Tero

• Department of Mathematics and Statistics, University of Turku, Finland

autor

Sahla Esa

• Department of Mathematics and Statistics, University of Turku, Finland

Bibliografia

• [1] Ginsburg S, Spanier E. Mappings of languages by two-tape devices. Journal of the ACM, 1965. 12:423-434. doi:10.1145/321281.321294.
• [2] Berstel J, Boasson L, Carton O, Pin J, Restivo A. The expressive power of the shuffle product. Information and Computation, 2010. 208:1258-1272. doi:10.1016/j.ic.2010.06.002.
• [3] Ito M. Algebraic Theory of Automata and Languages. World Scientific, Singapore, 2004. doi:10.1142/4791. ISBN:978-981-02-4727-0.
• [4] Beek M, Kleijn J. Associativity of Infinite Synchronized Shuffles and Team Automata. Fundam. Inform., 2009. 91(3-4):437-461. doi:10.3233/FI-2009-0051.
• [5] Câmpeanu C, Salomaa K, Vágvölgyi S. Shuffle Decompositions of Regular Languages. Int. J. Found. Comput. Sci., 2002. 13(6):799-816. doi:10.1142/S0129054102001461.
• [6] Henshall D, Rampersad N, Shallit J. Shuffling and Unshuffling. Bulletin of the EATCS, 2012. (107):131-142. 1106.5767v4.
• [7] Hopcroft JE, Ullman JD. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Mass., 1979. ISBN:020102988X, 9780201029888.
• [8] Salomaa A. Formal Languages. Academic Press, New York, 1973. ISSN:0572-4252.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).