Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
An Exercise in Mathematical Engineering: Stating and Proving Kuratowski Theorem Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Inverse Monoids of Higher-Dimensional Strings

Author : David Janin

Published in: Theoretical Aspects of Computing - ICTAC 2015

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Halfway between graph transformation theory and inverse semigroup theory, we define higher dimensional strings as bi-deterministic graphs with distinguished sets of input roots and output roots. We show that these generalized strings can be equipped with an associative product so that the resulting algebraic structure is an inverse semigroup. Its natural order is shown to capture existence of root preserving graph morphism. A simple set of generators is characterized. As a subsemigroup example, we show how all finite grids are finitely generated. Finally, simple additional restrictions on products lead to the definition of subclasses with decidable Monadic Second Order (MSO) language theory.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Quotienting the Delay Monad by Weak Bisimilarity
next chapter A Functorial Bridge Between the Infinitary Affine Lambda-Calculus and Linear Logic
Footnotes
1
unambiguity can be generalized to hypergraphs by viewing every binary relation of the form \(\exists \mathbf {z_1} \mathbf {z_2} \mathbf {z_3}\, a(\mathbf {z_1},x,\mathbf {z_2},y,\mathbf {z_3})\) with tuples of FO-variables \(\mathbf {z_1}\), \(\mathbf {z_2}\) and \(\mathbf {z_3}\) of adequate lengths as a primitive binary relation.
 
Literature
1.
2.
Abrial, J.-R.: Modeling in Event-B - System and Software Engineering. Cambridge University Press, Cambridge (2010)CrossRefMATH
3.
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)CrossRefMATH
4.
Blume, C., Bruggink, H.J.S., Friedrich, M., König, B.: Treewidth, pathwidth and cospan decompositions with applications to graph-accepting tree automata. J. Visual Lang. Comput. 24(3), 192–206 (2013)CrossRef
5.
Blumensath, A., Janin, D.: A syntactic congruence for languages of birooted trees. Semigroup Forum 91(161), 1–24 (2014)MathSciNetMATH
6.
Bruggink, H.J.S., König, B.: On the recognizability of arrow and graph languages. In: Ehrig, H., Heckel, R., Rozenberg, G., Taentzer, G. (eds.) ICGT 2008. LNCS, vol. 5214, pp. 336–350. Springer, Heidelberg (2008) CrossRef
7.
Burmeister, P.: A Model Theoretic Oriented Approach to Partial Algebras. Akademie-Verlag, Berlin (1986) MATH
8.
Courcelle, B.: The monadic second-order logic of graphs V: on closing the gap between definability and recognizability. Theor. Comp. Sci. 80(2), 153–202 (1991)MathSciNetCrossRefMATH
9.
Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-order Logic, A Language Theoretic Approach, of Encyclopedia of Mathematics and its Applications, vol. 138. Cambridge University Press, Cambridge (2012) CrossRefMATH
10.
11.
12.
13.
Gadducci, F., Heckel, R.: An inductive view of graph transformation. In: Recent Trends in Algebraic Development Techniques, 12th International Workshop, WADT 1997, Selected Papers, pp. 223–237 (1997)
14.
Hudak, P., Janin, D.: Tiled polymorphic temporal media. In: Work on Functional Art, Music, Modeling and Design (FARM), pp. 49–60. ACM Press (2014)
15.
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)
16.
Janin, D.: Overlapping tile automata. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol. 7913, pp. 431–443. Springer, Heidelberg (2013) CrossRef
17.
18.
Janin, D.: Towards a higher-dimensional string theory for the modeling of computerized systems. In: Geffert, V., Preneel, B., Rovan, B., Štuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 7–20. Springer, Heidelberg (2014) CrossRef
19.
Janin, D.: Free inverse monoids up to rewriting. Research report, LaBRI, Université de Bordeaux (2015)
20.
Janin, D.: Walking automata in the free inverse monoid. Research report, LaBRI, Université de Bordeaux (2015)
21.
Janin, D., Berthaut, F., Desainte-Catherine, M.: Multi-scale design of interactive music systems: the libTuiles experiment. In: Sound and Music Computing (SMC) (2013)
22.
Janin, D., Berthaut, F., DeSainte-Catherine, M., Orlarey, Y., Salvati, S.: The T-calculus: towards a structured programming of (musical) time and space. In: Work on Functional Art, Music, Modeling and Design (FARM), pp. 23–34. ACM Press (2013)
23.
24.
25.
26.
Lawson, M.V.: Inverse Semigroups: The Theory of Partial Symmetries. World Scientific, River Edge (1998)CrossRefMATH
27.
Lewis, H.R.: A new decidable problem, with applications (extended abstract). In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 62–73. IEEE Press (1977)
28.
Margolis, S.W., Meakin, J.C.: E-unitary inverse monoids and the Cayley graph of a group presentation. J. Pure Appl. Algebra 58, 46–76 (1989)MathSciNetCrossRefMATH
29.
Meakin, J.: Groups and semigroups: connections and contrasts. In: Groups St Andrews 2005, London Mathematical Society, Lecture Note Series 340, vol. 2. Cambridge University Press (2007)
30.
31.
32.
Thomas, W.: Ehrenfeucht games, the composition method, and the monadic theory of ordinal words. In: Mycielski, J., Rozenberg, G., Salomaa, A. (eds.) Structures in Logic and Computer Science. LNCS, vol. 1261, pp. 118–143. Springer, Heidelberg (1997) CrossRef
33.
Thomas, W.: Logic for computer science: the engineering challenge. In: Wilhelm, R. (ed.) Informatics. LNCS, vol. 2000, pp. 257–267. Springer, Heidelberg (2001) CrossRef
Metadata
Title
Inverse Monoids of Higher-Dimensional Strings
Author
David Janin
Copyright Year
2015
Book
Theoretical Aspects of Computing - ICTAC 2015

Print ISBN: 978-3-319-25149-3

Electronic ISBN: 978-3-319-25150-9

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-25150-9_9

Premium Partner

    Image Credits