Skip to main content
Erschienen in: Applicable Algebra in Engineering, Communication and Computing 5/2021

09.01.2020 | Original Paper

A positive extension of Eilenberg’s variety theorem for non-regular languages

verfasst von: A. Cano, J. Cantero, A. Martínez-Pastor

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 5/2021

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this paper we go further with the study initiated by Behle, Krebs and Reifferscheid (in: Proceedings CAI 2011, Lecture Notes in Computer Science, vol 6742, pp 97–114, 2011), who gave an Eilenberg-type theorem for non-regular languages via typed monoids. We provide a new extension of that result, inspired by the one carried out by Pin in the regular case in 1995, who considered classes of languages not necessarily closed under complement. We introduce the so-called positively typed monoids, and give a correspondence between varieties of such algebraic structures and positive varieties of possibly non-regular languages. We also prove a similar result for classes of languages with weaker closure properties.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Literatur
1.
Zurück zum Zitat Ballester-Bolinches, A., Pin, J.É., Soler-Escrivà, X.: Formations of finite monoids and formal languages: Eilenberg’s variety theorem revisited. Forum Math. 26(6), 1737–1761 (2014)MathSciNetCrossRef Ballester-Bolinches, A., Pin, J.É., Soler-Escrivà, X.: Formations of finite monoids and formal languages: Eilenberg’s variety theorem revisited. Forum Math. 26(6), 1737–1761 (2014)MathSciNetCrossRef
2.
Zurück zum Zitat Behle, C., Krebs, A., Reifferscheid, S.: Typed monoids—an Eilenberg-like theorem for non regular languages. In: Proceedings CAI 2011. Lecture Notes in Computer Science, vol. 6742, pp. 97–114 (2011) Behle, C., Krebs, A., Reifferscheid, S.: Typed monoids—an Eilenberg-like theorem for non regular languages. In: Proceedings CAI 2011. Lecture Notes in Computer Science, vol. 6742, pp. 97–114 (2011)
3.
Zurück zum Zitat Cadilhac, M., Krebs, A., McKenzie, P.: The algebraic theory of Parikh automata. Theory Comput. Syst. 62, 1241–1268 (2018)MathSciNetCrossRef Cadilhac, M., Krebs, A., McKenzie, P.: The algebraic theory of Parikh automata. Theory Comput. Syst. 62, 1241–1268 (2018)MathSciNetCrossRef
4.
Zurück zum Zitat Cano, A., Jurvanen, E.: Varieties of languages and frontier check. In: Proceedings of 13th International Conference on Automata and Formal Languages AFL2011, pp. 153–167 (2011) Cano, A., Jurvanen, E.: Varieties of languages and frontier check. In: Proceedings of 13th International Conference on Automata and Formal Languages AFL2011, pp. 153–167 (2011)
5.
Zurück zum Zitat Cano Gómez, A., Steinby, M.: Generalized contexts and n-ary syntactic semigroups of tree languages. Asian Eur. J. Math. 4, 49–79 (2011)MathSciNetCrossRef Cano Gómez, A., Steinby, M.: Generalized contexts and n-ary syntactic semigroups of tree languages. Asian Eur. J. Math. 4, 49–79 (2011)MathSciNetCrossRef
6.
Zurück zum Zitat Chaubard, L., Pin, J.É., Straubing, H.: First order formulas with modular predicates. In: Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science (LICS 2006), pp. 211–220. IEEE (2006) Chaubard, L., Pin, J.É., Straubing, H.: First order formulas with modular predicates. In: Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science (LICS 2006), pp. 211–220. IEEE (2006)
7.
Zurück zum Zitat Cano Gómez, A.: Semigroupes ordonnés et opérations sur les langages rationnels. Ph.D. Thesis, Université Paris 7 and Departamento de Sistemas Informáticos y Computación, Universidad Politécnica de Valencia (2003) Cano Gómez, A.: Semigroupes ordonnés et opérations sur les langages rationnels. Ph.D. Thesis, Université Paris 7 and Departamento de Sistemas Informáticos y Computación, Universidad Politécnica de Valencia (2003)
8.
Zurück zum Zitat Cano Gómez, A., Pin, J.É.: Shuffle on positive varieties of languages. Theor. Comput. Sci. 312, 433–461 (2004)MathSciNetCrossRef Cano Gómez, A., Pin, J.É.: Shuffle on positive varieties of languages. Theor. Comput. Sci. 312, 433–461 (2004)MathSciNetCrossRef
9.
Zurück zum Zitat Eilenberg, S.: Automata, Languages and Machines, vol. B. Academic Press, New York (1976)MATH Eilenberg, S.: Automata, Languages and Machines, vol. B. Academic Press, New York (1976)MATH
10.
Zurück zum Zitat Klaedtke, F., Rueß, H.: Monadic second-order logics with cardinalities. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) Automata, Languages and Programming. ICALP 2003. Lect. Notes Comput. Sci., vol. 2719, pp. 681–696. Springer, Heidelberg (2003) Klaedtke, F., Rueß, H.: Monadic second-order logics with cardinalities. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) Automata, Languages and Programming. ICALP 2003. Lect. Notes Comput. Sci., vol. 2719, pp. 681–696. Springer, Heidelberg (2003)
11.
Zurück zum Zitat Krebs, A., Lange, K.J., Reifferscheid, S.: Characterizing \(TC^0\) in terms of infinite groups. Theory Comput. Syst. 40(4), 303–325 (2007)MathSciNetCrossRef Krebs, A., Lange, K.J., Reifferscheid, S.: Characterizing \(TC^0\) in terms of infinite groups. Theory Comput. Syst. 40(4), 303–325 (2007)MathSciNetCrossRef
12.
Zurück zum Zitat Pin, J.É.: Syntactic semigroups. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1 (chap. 10). Springer, Berlin (1997) Pin, J.É.: Syntactic semigroups. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1 (chap. 10). Springer, Berlin (1997)
13.
Zurück zum Zitat Pin, J.É.: Varieties of Formal Languages. Plenum Pub. Corp, New York (1986)CrossRef Pin, J.É.: Varieties of Formal Languages. Plenum Pub. Corp, New York (1986)CrossRef
14.
Zurück zum Zitat Pin, J.É.: A variety theorem without complementation. Russ. Math. (Iz. VUZ) 39, 74–83 (1995) Pin, J.É.: A variety theorem without complementation. Russ. Math. (Iz. VUZ) 39, 74–83 (1995)
15.
16.
Zurück zum Zitat Polák, L.: A classification of rational languages by semilattice-ordered monoids. Arch. Math. (Brno) 40, 395–406 (2004)MathSciNetMATH Polák, L.: A classification of rational languages by semilattice-ordered monoids. Arch. Math. (Brno) 40, 395–406 (2004)MathSciNetMATH
17.
Zurück zum Zitat Sakarovitch, J.: An algebraic framework for the study of the syntactic monoids application to the group languages. In: Mazurkiewic, A. (ed.) MFCS, pp. 510–516. Springer, Heidelberg (1976) Sakarovitch, J.: An algebraic framework for the study of the syntactic monoids application to the group languages. In: Mazurkiewic, A. (ed.) MFCS, pp. 510–516. Springer, Heidelberg (1976)
18.
Zurück zum Zitat Salamanca, J.: Unveiling Eilenberg-type Correspondences: Birkhoff’s theorem for (finite) algebras + duality. arXiv:1702.02822 (2017) Salamanca, J.: Unveiling Eilenberg-type Correspondences: Birkhoff’s theorem for (finite) algebras + duality. arXiv:​1702.​02822 (2017)
19.
Zurück zum Zitat Steinby, M.: A theory of tree language varieties. In: Nivat, M., Podelski, A. (eds.) Tree Automata and Languages, pp. 57–81. North-Holland, Amsterdam (1992)MATH Steinby, M.: A theory of tree language varieties. In: Nivat, M., Podelski, A. (eds.) Tree Automata and Languages, pp. 57–81. North-Holland, Amsterdam (1992)MATH
20.
Zurück zum Zitat Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkh’auser, Boston (1994)CrossRef Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkh’auser, Boston (1994)CrossRef
21.
Zurück zum Zitat Straubing, H.: On logical descriptions of regular languages. In: Rajsbaum, S. (ed.) LATIN 2002. Lect. Notes Comput. Sci., vol. 2286, pp. 528–538. Springer, Berlin (2002) Straubing, H.: On logical descriptions of regular languages. In: Rajsbaum, S. (ed.) LATIN 2002. Lect. Notes Comput. Sci., vol. 2286, pp. 528–538. Springer, Berlin (2002)
22.
Zurück zum Zitat Urbat, H., Admek, J., Chen, L., Milius, S.: Eilenberg theorems for free. In: Larsen, K.M., Bodlaender, H.L., Raskin, J.F. (eds.) MFCS 2017, vol. 83, pp. 43:1–43:15. LIPIcs, Leibnitz (2017). arXiv:1602.05831 Urbat, H., Admek, J., Chen, L., Milius, S.: Eilenberg theorems for free. In: Larsen, K.M., Bodlaender, H.L., Raskin, J.F. (eds.) MFCS 2017, vol. 83, pp. 43:1–43:15. LIPIcs, Leibnitz (2017). arXiv:​1602.​05831
Metadaten
Titel
A positive extension of Eilenberg’s variety theorem for non-regular languages
verfasst von
A. Cano
J. Cantero
A. Martínez-Pastor
Publikationsdatum
09.01.2020
Verlag
Springer Berlin Heidelberg
Erschienen in
Applicable Algebra in Engineering, Communication and Computing / Ausgabe 5/2021
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-020-00414-2

Weitere Artikel der Ausgabe 5/2021

Applicable Algebra in Engineering, Communication and Computing 5/2021 Zur Ausgabe