Skip to main content
Registrieren
Springer Professional
SUCHE
MENÜ 1 2 3 4
main-content
nach oben

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

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, um Zugang zu erhalten
share
TEILEN

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.
Nächster Artikel Constructing reductions for creative telescoping

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 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

Testen Sie jetzt 15 Tage kostenlos.

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 15 Tage kostenlos.

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 15 Tage kostenlos.

Jetzt informieren
Literatur
1.
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.
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.
Cadilhac, M., Krebs, A., McKenzie, P.: The algebraic theory of Parikh automata. Theory Comput. Syst. 62, 1241–1268 (2018) MathSciNetCrossRef
4.
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.
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.
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.
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.
Cano Gómez, A., Pin, J.É.: Shuffle on positive varieties of languages. Theor. Comput. Sci. 312, 433–461 (2004) MathSciNetCrossRef
9.
Eilenberg, S.: Automata, Languages and Machines, vol. B. Academic Press, New York (1976) MATH
10.
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.
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.
Pin, J.É.: Syntactic semigroups. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1 (chap. 10). Springer, Berlin (1997)
13.
Pin, J.É.: Varieties of Formal Languages. Plenum Pub. Corp, New York (1986) CrossRef
14.
Pin, J.É.: A variety theorem without complementation. Russ. Math. (Iz. VUZ) 39, 74–83 (1995)
15.
16.
Polák, L.: A classification of rational languages by semilattice-ordered monoids. Arch. Math. (Brno) 40, 395–406 (2004) MathSciNetMATH
17.
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.
19.
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.
Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkh’auser, Boston (1994) CrossRef
21.
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.
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

Original Paper

Constructing reductions for creative telescoping

Original Paper

Discrete Gaussian measures and new bounds of the smoothing parameter for lattices

OriginalPaper

Cyclic codes over with respect to the homogeneous weight and their applications to DNA codes

Original Paper

Construction of new quantum codes derived from constacyclic codes over

Premium Partner

    Version: 0.1954.0