Abstract
Overlapping tile automata and the associated notion of recognizability by means of (adequate) premorphisms in finite ordered monoids have recently been defined for coping with the collapse of classical recognizability in inverse monoids. In this paper, we investigate more in depth the associated algebraic tools that allow for a better understanding of the underlying mathematical theory. In particular, addressing the surprisingly difficult problem of language product, we eventually found some deep links with classical notions of inverse semigroup theory such as the notion of restricted product.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cornock, C., Gould, V.: Proper two-sided restriction semigroups and partial actions. Journal of Pure and Applied Algebra 216, 935–949 (2012)
Dicky, A., Janin, D.: Embedding finite and infinite words into overlapping tiles. Tech. Rep. RR-1475-13, LaBRI, Université de Bordeaux, Bordeaux (2013)
Dicky, A., Janin, D.: Modélisation algébrique du diner des philosophes. Modélisation des Systèmes Réactifs (MSR). Journal Européen des Systèmes Automatisés (JESA) 47(1-2-3/2013) (November 2013)
Fountain, J.: Right PP monoids with central idempotents. Semigroup Forum 13, 229–237 (1977)
Fountain, J., Gomes, G., Gould, V.: The free ample monoid. Int. Jour. of Algebra and Computation 19, 527–554 (2009)
Hollings, C.D.: From right PP monoids to restriction semigroups: a survey. European Journal of Pure and Applied Mathematics 2(1), 21–57 (2009)
Hollings, C.D.: The Ehresmann-Schein-Nambooripad Theorem and its successors. European Journal of Pure and Applied Mathematics 5(4), 414–450 (2012)
Janin, D.: Quasi-recognizable vs MSO definable languages of one-dimensional overlapping tiles. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 516–528. Springer, Heidelberg (2012)
Janin, D.: Algebras, automata and logic for languages of labeled birooted trees. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol. 7966, pp. 312–323. Springer, Heidelberg (2013)
Janin, D.: On languages of one-dimensional overlapping tiles. In: van Emde Boas, P., Groen, F.C.A., Italiano, G.F., Nawrocki, J., Sack, H. (eds.) SOFSEM 2013. LNCS, vol. 7741, pp. 244–256. Springer, Heidelberg (2013)
Janin, D.: Overlapping tile automata. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol. 7913, pp. 431–443. Springer, Heidelberg (2013)
Janin, D., Berthaut, F., DeSainte-Catherine, M., Orlarey, Y., Salvati, S.: The T-calculus : towards a structured programming of (musical) time and space. In: Workshop on Functional Art, Music, Modeling and Design (FARM). ACM Press (2013)
Janin, D., Berthaut, F., DeSainteCatherine, M.: Multi-scale design of interactive music systems: the libTuiles experiment. In: Sound and Music Computing (SMC) (2013)
Kellendonk, J.: The local structure of tilings and their integer group of coinvariants. Comm. Math. Phys. 187, 115–157 (1997)
Kellendonk, J., Lawson, M.V.: Tiling semigroups. Journal of Algebra 224(1), 140–150 (2000)
Lawson, M.V.: Semigroups and ordered categories. I. the reduced case. Journal of Algebra 141(2), 422–462 (1991)
Lawson, M.V.: Inverse Semigroups: The theory of partial symmetries. World Scientific (1998)
Lawson, M.V.: McAlister semigroups. Journal of Algebra 202(1), 276–294 (1998)
Margolis, S.W., Meakin, J.C.: Inverse monoids, trees and context-free languages. Trans. Amer. Math. Soc. 335, 259–276 (1993)
Munn, W.D.: Free inverse semigroups. Proceeedings of the London Mathematical Society 29(3), 385–404 (1974)
Pietrich, M.: Inverse semigroups. Wiley (1984)
Pin, J.E.: Algebraic tools for the concatenation product. Theoretical Comp. Science 292(1), 317–342 (2003)
Scheiblich, H.E.: Free inverse semigroups. Semigroup Forum 4, 351–359 (1972)
Silva, P.V.: On free inverse monoid languages. ITA 30(4), 349–378 (1996)
Thomas, W.: Handbook of Formal Languages. In: Languages, Automata, and Logic, ch. 7, vol. III, pp. 389–455. Springer, Heidelberg (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Dubourg, E., Janin, D. (2014). Algebraic Tools for the Overlapping Tile Product. In: Dediu, AH., Martín-Vide, C., Sierra-Rodríguez, JL., Truthe, B. (eds) Language and Automata Theory and Applications. LATA 2014. Lecture Notes in Computer Science, vol 8370. Springer, Cham. https://doi.org/10.1007/978-3-319-04921-2_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-04921-2_27
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04920-5
Online ISBN: 978-3-319-04921-2
eBook Packages: Computer ScienceComputer Science (R0)