Two-way Automata and Regular Languages of Overlapping Tiles

• Autorzy: Dicky A. , Janin D.

Identyfikatory

DOI

10.3233/FI-2015-1278

• Języki publikacji: EN

Abstrakty

EN

We consider classes of languages of overlapping tiles, i.e., subsets of the McAlister monoid: the class REG of languages definable by Kleene’s regular expressions, the class MSO of languages definable by formulas of monadic second-order logic, and the class REC of languages definable by morphisms into finite monoids. By extending the semantics of finite-state two-way automata (possibly with pebbles) from languages of words to languages of tiles, we obtain a complete characterization of the classes REG and MSO. In particular, we show that adding pebbles strictly increases the expressive power of two-way automata recognizing languages of tiles, but the hierarchy induced by the number of allowed pebbles collapses to level one.

Słowa kluczowe

EN

two-way automata; word languages; overlapping tile languages; regular languages; McAlister inverse monoid

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 141, nr 4
• Strony: 311--343
• Opis fizyczny: Bibliogr. 49 poz.

Twórcy

autor

Dicky A.

• Université de Bordeaux, LaBRI UMR 5800 351, cours de la Libération, F-33405 Talence, France

autor

Janin D.

• Université de Bordeaux, LaBRI UMR 5800 351, cours de la Libération, F-33405 Talence, France

Bibliografia

• [1] F. S. Almeida. Algebraic Aspects of Tiling Semigroups. PhD Thesis, Universidade de Lisboa, Faculdade de Ciências Departamento de Matemática, Lisboa, Portugal, 2010.
• [2] M. Anselmo. Automates et code zigzag. ITA, 25:49–66, 1991.
• [3] J. Berstel. Transductions and Context-Free Languages. Teubner Verlag, 1979.
• [4] F. Berthaut, D. Janin, and B. Martin. Advanced synchronization of audio or symbolic musical patterns: an algebraic approach. International Journal of Semantic Computing, 6(4):409–427, 12 2012.
• [5] J.-C. Birget. Concatenation of inputs in a two-way automaton. Theor. Comp. Sci., 63(2):141 – 156, 1989.
• [6] B. Courcelle and J. Engelfriet. Graph structure and monadic second-order logic, a language theoretic approach, volume 138 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2012.
• [7] A. Dicky and D. Janin. Embedding finite and infinite words into overlapping tiles. In Developments in Language Theory (DLT), volume 8633 of LNCS, pages 339–347. Springer, 10 2014.
• [8] Do Long Van, B. LeSaëc, and I. Litovsky. On coding morphisms for zigzag codes. ITA, 26:565–580, 1992.
• [9] E. Dubourg and D. Janin. Algebraic tools for the overlapping tile product. In Language and Automata Theory and Applications (LATA), volume 8370 of LNCS, pages 335 – 346. Springer, 03 2014.
• [10] J. Engelfriet, H. J. Hoogeboom, and J.-P. Van Best. Trips on trees. Acta Cybern., 14(1):51–64, 1999.
• [11] J. Engelfriet, H. J. Hoogeboom, and B. Samwel. XML transformation by tree-walking transducers with invisible pebbles. In Principles of Database System (PODS). ACM, 2007.
• [12] J. Engelfriet and H.J. Hoogeboom. Tree-walking pebble automata. In J. Karhumäki, H.Maurer, G. Paun, and G. Rozenberg, editors, Jewels are forever, contributions to Theoretical Computer Science in honor of Arto Salomaa, pages 72–83. Springer, 1999.
• [13] J. Engelfriet and H.J. Hoogeboom. Automata with nested pebbles capture first-order logic with transitive closure. Logical Methods in Computer Science, 3, 2007.
• [14] J. Fountain, G. Gomes, and V. Gould. The free ample monoid. Int. Jour. of Algebra and Comp., 19:527–554, 2009.
• [15] S. Fratani and G. Sénizergues. Iterated pushdown automata and sequences of rational numbers. Ann. Pure Appl. Logic, 141(3):363–411, 2006.
• [16] V. Geffert and L. Istonová. Translation fromclassical two-way automata to pebble two-way automata. RAIRO - Theor. Inf. and Applic., 44(4):507–523, 2010.
• [17] N. Globerman and D. Harel. Complexity results for two-way and multi-pebble automata and their logics. Theor. Comp. Sci., 169(2):161–184, 1996.
• [18] P. Hudak and D. Janin. Tiled polymorphic temporal media. In Work. on Functional Art, Music, Modeling and Design (FARM), pages 49–60. ACM Press, 2014.
• [19] D. Janin. Quasi-inverse monoids (and premorphisms). Research report RR-1459-12, LaBRI, Université de Bordeaux, 04 2012.
• [20] D. Janin. Quasi-recognizable vs MSO definable languages of one-dimensional overlapping tiles. In Mathematical Found. of Comp. Science (MFCS), volume 7464 of LNCS, pages 516–528, 09 2012.
• [21] D. Janin. Vers une modélisation combinatoire des structures rythmiques simples de la musique. Revue Francophone d’InformatiqueMusicale (RFIM), 2, 09 2012.
• [22] D. Janin. Algebras, automata and logic for languages of labeled birooted trees. In Int. Col. on Aut., Lang. and Programming (ICALP), volume 7966 of LNCS, pages 318–329. Springer, 07 2013.
• [23] D. Janin. On languages of one-dimensional overlapping tiles. In Int. Conf. on Current Trends in Theo. and Prac. of Comp. Science (SOFSEM), volume 7741 of LNCS, pages 244–256. Springer, 01 2013.
• [24] D. Janin. Overlaping tile automata. In 8th Int. Computer Science Symp. in Russia (CSR), volume 7913 of LNCS, pages 431–443. Springer, 06 2013.
• [25] D. Janin. On languages of labeled birooted trees: Algebras, automata and logic. Information and Computation, 2014.
• [26] D. Janin. Walking automata in the free inverse monoid. Research report, LaBRI, Université de Bordeaux, 2015.
• [27] D. Janin, F. Berthaut, and M. Desainte-Catherine. Multi-scale design of interactive music systems : the libTuiles experiment. In Sound and Music Comp. (SMC), 2013.
• [28] D. Janin, F. Berthaut,M. DeSainte-Catherine, Y. Orlarey, and S. Salvati. The T-calculus : towards a structured programming of (musical) time and space. InWork. on Functional Art, Music,Modeling and Design (FARM), pages 23–34. ACM Press, 2013.
• [29] J. Kellendonk. The local structure of tilings and their integer group of coinvariants. Comm. Math. Phys., 187:115–157, 1997.
• [30] J. Kellendonk and M. V. Lawson. Tiling semigroups. Journal of Algebra, 224(1):140 – 150, 2000.
• [31] J. Kellendonk and M. V. Lawson. Universal groups for point-sets and tilings. Journal of Algebra, 276:462–492, 2004.
• [32] M. Kunc and A. Okhotin. Describing periodicity in two-way deterministic finite automata using transformation semigroups. In Developments in Language Theory (DLT), volume 6795 of LNCS, pages 324–336. Springer, 2011.
• [33] M. V. Lawson. Inverse Semigroups : The theory of partial symmetries. World Scientific, 1998.
• [34] M. V. Lawson. McAlister semigroups. Journal of Algebra, 202(1):276 – 294, 1998.
• [35] B. LeSaëc, I. Litovsky, and B. Patrou. A more efficient notion of zigzag stability. ITA, 30(3):181–194, 1996.
• [36] S.W.Margolis and J.-E. Pin. Languages and inverse semigroups. In Int. Col. on Aut., Lang. and Programming (ICALP), volume 172 of LNCS, pages 337–346. Springer, 1984.
• [37] D.B. McAlister. Inverse semigroups which are separated over a subsemigroups. Trans. Amer. Math. Soc., 182:85–117, 1973.
• [38] W. D. Munn. Free inverse semigroups. Proceeedings of the London Mathematical Society, 29(3):385–404, 1974.
• [39] J.-P. Pécuchet. Automates boustrophedon, semi-groupe de Birget et monoide inversif libre. ITA, 19(1):71–100, 1985.
• [40] M. Petrich. Inverse semigroups. Wiley, 1984.
• [41] J-.E. Pin. Chap. 10. Syntactic semigroups. In G. Rozenberg and A. Salomaa, editors, Handbook of formal languages, Vol. I, pages 679–746. Springer-Verlag, 1997.
• [42] M. O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3(2):114 –125, april 1959.
• [43] J. Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009.
• [44] H. E. Scheiblich. Free inverse semigroups. Semigroup Forum, 4:351–359, 1972.
• [45] J. C. Shepherdson. The reduction of two-way automata to one-way automata. IBM J. Res. Dev., 3:198–200, April 1959.
• [46] P. V. Silva. On free inverse monoid languages. ITA, 30(4):349–378, 1996.
• [47] W. Thomas. Chap. 7. Languages, automata, and logic. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, Vol. III, pages 389–455. Springer-Verlag, Berlin Heidelberg, 1997.
• [48] M. Y. Vardi. A note on the reduction of two-way automata to one-way automata. Information Processing Letters, 30:261–264, 1989.
• [49] D.J. Weir. Characterizing mildly context-sensitive grammar formalisms. PhD thesis, University of Pennsylvania, 1988.