×

On labeled birooted tree languages: algebras, automata and logic. (English) Zbl 1353.68187

Summary: With an aim to developing expressive language theoretical tools applicable to inverse semigroup languages, that is, subsets of inverse semigroups, this paper explores the language theory of finite labeled birooted trees: Munn’s birooted trees extended with vertex labeling. To this purpose, we define a notion of finite state birooted tree automata that simply extends finite state word automata semantics. This notion is shown to capture the class of languages that are definable in Monadic Second Order Logic and upward closed with respect to the natural order. Then, we derive from these automata the notion of quasi-recognizable languages, that is, languages recognizable by means of (adequate) premorphisms into finite (adequately) ordered monoids. This notion is shown to capture finite Boolean combinations of languages as above, a class that contains classical regular languages of finite (mono-rooted) trees. This contrasts with the known collapse of classical algebraic tools when applied to inverse semigroups.

MSC:

68Q70 Algebraic theory of languages and automata
03D05 Automata and formal grammars in connection with logical questions
20M35 Semigroups in automata theory, linguistics, etc.

Software:

Rodin
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abrial, J.-R., Modeling in Event-B - System and Software Engineering (2010), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1213.68214
[2] Berthaut, F.; Janin, D.; Martin, B., Advanced synchronization of audio or symbolic musical patterns: an algebraic approach, Int. J. Semant. Comput., 6, 4, 409-427 (2012) · Zbl 1284.00055
[3] Blumensath, A., Recognisability for algebras of infinite trees, Theor. Comput. Sci., 412, 29, 3463-3486 (2011) · Zbl 1233.68159
[4] Blumensath, A.; Janin, D., A syntactic congruence for languages of birooted trees (2014), LaBRI, Université de Bordeaux, Research report RR-1478-14 · Zbl 1333.68185
[5] Bojańczyk, M., Tree-walking automata, (2nd Int. Conf. on Language and Automata Theory and Applications. 2nd Int. Conf. on Language and Automata Theory and Applications, LATA. 2nd Int. Conf. on Language and Automata Theory and Applications. 2nd Int. Conf. on Language and Automata Theory and Applications, LATA, Lect. Notes Comput. Sci., vol. 5196 (2008), Springer) · Zbl 1156.68445
[6] Bojanczyk, M.; Straubing, H.; Walukiewicz, I., Wreath products of forest algebras, with applications to tree logics, Log. Methods Comput. Sci., 8, 3 (2012) · Zbl 1258.03044
[7] Bojańczyk, M.; Walukiewicz, I., Forest algebras, (Logic and Automata (2008), Amsterdam University Press), 107-132 · Zbl 1217.68123
[8] Burmeister, P., A Model Theoretic Oriented Approach to Partial Algebras (1986), Akademie-Verlag · Zbl 0598.08004
[9] Chalopin, J.; Métivier, Y., An efficient message passing election algorithm based on Mazurkiewicz’s algorithm, Fundam. Inform., 80, 1-3, 221-246 (2007) · Zbl 1137.68326
[10] Courcelle, B.; Engelfriet, J., Graph Structure and Monadic Second-Order Logic, a Language Theoretic Approach, Encycl. Math. Appl., vol. 138 (2012), Cambridge University Press · Zbl 1257.68006
[11] Deis, T.; Meakin, J.; Sénizergues, G., Equations in free inverse monoids, Int. J. Algebra Comput., 17, 4, 761-795 (2007) · Zbl 1158.20028
[12] Desain, P.; Honing, H., LOCO: a composition microworld in Logo, Comput. Music J., 12, 3, 30-42 (1988)
[13] Dicky, A.; Janin, D., Two-way automata and regular languages of overlapping tiles (2013), LaBRI, Université de Bordeaux, Research report RR-1463-12 · Zbl 1348.68101
[14] Dubourg, E.; Janin, D., Algebraic tools for the overlapping tile product, (Language and Automata Theory and Applications. Language and Automata Theory and Applications, LATA. Language and Automata Theory and Applications. Language and Automata Theory and Applications, LATA, Lect. Notes Comput. Sci., vol. 8370 (2014), Springer), 335-346 · Zbl 1407.68250
[15] Ésik, Z.; Weil, P., On logically defined recognizable tree languages, (Found. of Soft. Tech. and Theor. Comp. Science. Found. of Soft. Tech. and Theor. Comp. Science, FSTTCS (2003)), 195-207 · Zbl 1196.68149
[16] Fountain, J., Right PP monoids with central idempotents, Semigroup Forum, 13, 229-237 (1977) · Zbl 0353.20051
[17] Fountain, J., Adequate semigroups, Proc. Edinb. Math. Soc., 22, 2, 113-125 (1979) · Zbl 0414.20048
[18] Fountain, J.; Gomes, G.; Gould, V., The free ample monoid, Int. J. Algebra Comput., 19, 527-554 (2009) · Zbl 1192.20041
[19] Gould, V., Restriction and Ehresmann semigroups, (Proceedings of the International Conference on Algebra 2010 (2010), World Scientific) · Zbl 1264.20067
[20] Hoare, C. A.R., Communicating Sequential Processing, Prentice-Hall Int. Ser. Comput. Sci. (1985), Prentice-Hall International · Zbl 0637.68007
[21] Hollings, C. D., From right PP monoids to restriction semigroups: a survey, Eur. J. Pure Appl. Math., 2, 1, 21-57 (2009) · Zbl 1214.20056
[22] Hollings, C. D., The Ehresmann-Schein-Nambooripad theorem and its successors, Eur. J. Pure Appl. Math., 5, 4, 414-450 (2012) · Zbl 1389.20078
[23] Hudak, P., An algebraic theory of polymorphic temporal media, (Proceedings of PADL’04: 6th International Workshop on Practical Aspects of Declarative Languages. Proceedings of PADL’04: 6th International Workshop on Practical Aspects of Declarative Languages, Lect. Notes Comput. Sci., vol. 3057 (June 2004), Springer-Verlag), 1-15
[24] Hudak, P., A sound and complete axiomatization of polymorphic temporal media (2008), Department of Computer Science, Yale University, Technical Report RR-1259
[25] Hudak, P.; Janin, D., Tiled polymorphic temporal media (2014), LaBRI, Université de Bordeaux, Research report RR-1478-14
[26] Janin, D., A lazy real-time system architecture for interactive music, (Actes des Journées d’informatique Musicale. Actes des Journées d’informatique Musicale, JIM (2012)), 133-139
[27] Janin, D., Quasi-inverse monoids (and premorphisms) (2012), LaBRI, Université de Bordeaux, Research report RR-1459-12
[28] Janin, D., Quasi-recognizable vs MSO definable languages of one-dimensional overlapping tiles, (Mathematical Found. of Comp. Science. Mathematical Found. of Comp. Science, MFCS. Mathematical Found. of Comp. Science. Mathematical Found. of Comp. Science, MFCS, Lect. Notes Comput. Sci., vol. 7464 (2012)), 516-528 · Zbl 1365.68334
[29] Janin, D., Vers une modélisation combinatoire des structures rythmiques simples de la musique, Rev. Francoph. Inform. Music. (RFIM), 2 (2012)
[30] Janin, D., Algebras, automata and logic for languages of labeled birooted trees, (Int. Col. on Aut., Lang. and Programming. Int. Col. on Aut., Lang. and Programming, ICALP. Int. Col. on Aut., Lang. and Programming. Int. Col. on Aut., Lang. and Programming, ICALP, Lect. Notes Comput. Sci., vol. 7966 (2013), Springer), 318-329 · Zbl 1335.68157
[31] Janin, D., On languages of one-dimensional overlapping tiles, (Int. Conf. on Current Trends in Theo. and Prac. of Comp. Science. Int. Conf. on Current Trends in Theo. and Prac. of Comp. Science, SOFSEM. Int. Conf. on Current Trends in Theo. and Prac. of Comp. Science. Int. Conf. on Current Trends in Theo. and Prac. of Comp. Science, SOFSEM, Lect. Notes Comput. Sci., vol. 7741 (2013), Springer), 244-256 · Zbl 1303.68078
[32] Janin, D., Overlaping tile automata, (8th International Computer Science Symposium in Russia. 8th International Computer Science Symposium in Russia, CSR. 8th International Computer Science Symposium in Russia. 8th International Computer Science Symposium in Russia, CSR, Lect. Notes Comput. Sci., vol. 7913 (2013), Springer), 431-443 · Zbl 1381.68118
[33] Janin, D., Walking automata in the free inverse monoid (2013), LaBRI, Université de Bordeaux, Research report RR-1464-12
[34] Janin, D., Towards a higher dimensional string theory for the modeling of computerized systems, (Int. Conf. on Current Trends in Theo. and Prac. of Comp. Science. Int. Conf. on Current Trends in Theo. and Prac. of Comp. Science, SOFSEM. Int. Conf. on Current Trends in Theo. and Prac. of Comp. Science. Int. Conf. on Current Trends in Theo. and Prac. of Comp. Science, SOFSEM, Lect. Notes Comput. Sci., vol. 8327 (2014), Springer), 7-20 · Zbl 1432.68033
[35] Janin, D.; Berthaut, F.; DeSainteCatherine, M., Multi-scale design of interactive music systems: the libTuiles experiment, (Sound and Music Computing. Sound and Music Computing, SMC (2013))
[36] Kellendonk, J., The local structure of tilings and their integer group of coinvariants, Commun. Math. Phys., 187, 115-157 (1997) · Zbl 0887.52013
[37] Kellendonk, J.; Lawson, M. V., Tiling semigroups, J. Algebra, 224, 1, 140-150 (2000) · Zbl 0971.20045
[38] Kellendonk, J.; Lawson, M. V., Universal groups for point-sets and tilings, J. Algebra, 276, 462-492 (2004) · Zbl 1080.20056
[39] Lawson, M. V., Semigroups and ordered categories. I. The reduced case, J. Algebra, 141, 2, 422-462 (1991) · Zbl 0747.18007
[40] Lawson, M. V., Inverse Semigroups: The Theory of Partial Symmetries (1998), World Scientific · Zbl 1079.20505
[41] Lawson, M. V., McAlister semigroups, J. Algebra, 202, 1, 276-294 (1998) · Zbl 0907.20051
[42] Lohrey, M.; Ondrusch, N., Inverse monoids: decidability and complexity of algebraic questions, Inf. Comput., 205, 8, 1212-1234 (2007) · Zbl 1139.20054
[43] Margolis, S. W.; Meakin, J. C., Inverse monoids, trees and context-free languages, Trans. Am. Math. Soc., 335, 259-276 (1993) · Zbl 0795.20043
[44] Margolis, S. W.; Pin, J.-E., Languages and inverse semigroups, (Int. Col. on Aut., Lang. and Programming. Int. Col. on Aut., Lang. and Programming, ICALP. Int. Col. on Aut., Lang. and Programming. Int. Col. on Aut., Lang. and Programming, ICALP, Lect. Notes Comput. Sci., vol. 172 (1984), Springer), 337-346 · Zbl 0566.68061
[45] McAlister, D. B., Inverse semigroups which are separated over a subsemigroups, Trans. Am. Math. Soc., 182, 85-117 (1973) · Zbl 0273.20046
[46] McAlister, D. B.; Reilly, N. R., E-unitary covers for inverse semigroups, Pac. J. Math., 68, 178-206 (1977) · Zbl 0368.20043
[47] Milner, R., Communication and Concurrency (1989), Prentice-Hall · Zbl 0683.68008
[48] Munn, W. D., Free inverse semigroups, Proc. Lond. Math. Soc., 29, 3, 385-404 (1974) · Zbl 0305.20033
[49] Pécuchet, J.-P., Automates boustrophedon, semi-groupe de Birget et monoide inversif libre, RAIRO Theor. Inform. Appl., 19, 1, 71-100 (1985) · Zbl 0604.68094
[50] Perrin, D.; Pin, J.-E., Semigroups and automata on infinite words, (Semigroups, Formal Languages and Groups. Semigroups, Formal Languages and Groups, NATO Advanced Study Institute (1995), Kluwer Academic), 49-72 · Zbl 0877.20045
[51] Perrin, D.; Pin, J.-E., Infinite Words: Automata, Semigroups, Logic and Games, Pure Appl. Math., vol. 141 (2004), Elsevier · Zbl 1094.68052
[52] Pietrich, M., Inverse Semigroups (1984), Wiley
[53] Pin, J.-E., Relational morphisms, transductions and operations on languages, (Formal Properties of Finite Automata and Applications. Formal Properties of Finite Automata and Applications, Lect. Notes Comput. Sci., vol. 386 (1989), Springer), 34-55
[54] Pin, J.-. E., Chap. 10. Syntactic semigroups, (Handbook of Formal Languages, vol. I (1997), Springer-Verlag), 679-746
[55] Pin, J.-E., Semigroupe version 2.0 (2009)
[56] Potthoff, A., First-order logic on finite trees, (Theory and Practice of Software Development. Theory and Practice of Software Development, TAPSOFT. Theory and Practice of Software Development. Theory and Practice of Software Development, TAPSOFT, Lect. Notes Comput. Sci., vol. 915 (1995), Springer), 125-139 · Zbl 1496.68178
[57] Rabin, M. O., Weakly definable relations and special automata, (Mathematical Logic and Foundation of Set Theory (1970), North-Holland), 1-23 · Zbl 0214.02208
[58] Scheiblich, H. E., Free inverse semigroups, Semigroup Forum, 4, 351-359 (1972) · Zbl 0259.20054
[59] Shelah, S., The monadic theory of order, Ann. Math., 102, 379-419 (1975) · Zbl 0345.02034
[60] Silva, P. V., On free inverse monoid languages, RAIRO Theor. Inform. Appl., 30, 4, 349-378 (1996) · Zbl 0867.68074
[61] Stephen, J. B., Presentations of inverse monoids, J. Pure Appl. Algebra, 63, 81-112 (1990) · Zbl 0691.20044
[62] Thomas, W., Chap. 7. Languages, automata, and logic, (Handbook of Formal Languages, vol. III (1997), Springer-Verlag: Springer-Verlag Berlin Heidelberg), 389-455
[63] Thomas, W., Logic for computer science: the engineering challenge, (Informatics - 10 Years Back, 10 Years Ahead. Informatics - 10 Years Back, 10 Years Ahead, Lect. Notes Comput. Sci., vol. 2000 (2001), Springer, Dagstuhl), 257-267
[64] Wilke, T., An algebraic theory for regular languages of finite and infinite words, Int. J. Algebra Comput., 3, 447-489 (1993) · Zbl 0791.68116
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.