Skip to main content

2020 | OriginalPaper | Buchkapitel

Geometrically Closed Positive Varieties of Star-Free Languages

verfasst von : Ondřej Klíma, Peter Kostolányi

Erschienen in: Language and Automata Theory and Applications

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

A recently introduced operation of geometrical closure on formal languages is investigated. It is proved that the geometrical closure of a language from the positive variety \(\mathcal {V}_{3/2}\), the level 3/2 of the Straubing-Thérien hierarchy of star-free languages, always falls into the variety \(\mathcal {R}_{LT}\), which is a new variety consisting of specific R-trivial languages. As a consequence, each class of regular languages lying between \(\mathcal {R}_{LT}\) and \(\mathcal {V}_{3/2}\) is geometrically closed.

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 "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!

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!

Literatur
1.
Zurück zum Zitat Almeida, J.: Finite Semigroups and Universal Algebra. World Scientific, Singapore (1994) Almeida, J.: Finite Semigroups and Universal Algebra. World Scientific, Singapore (1994)
2.
Zurück zum Zitat Arfi, M.: Opérations polynomiales et hiérarchies de concaténation. Theor. Comput. Sci. 91(1), 71–84 (1991)MathSciNetCrossRef Arfi, M.: Opérations polynomiales et hiérarchies de concaténation. Theor. Comput. Sci. 91(1), 71–84 (1991)MathSciNetCrossRef
4.
Zurück zum Zitat Blanpain, B., Champarnaud, J.M., Dubernard, J.P.: Geometrical languages. In: LATA 2007, pp. 127–138 (2007) Blanpain, B., Champarnaud, J.M., Dubernard, J.P.: Geometrical languages. In: LATA 2007, pp. 127–138 (2007)
5.
Zurück zum Zitat Bouajjani, A., Muscholl, A., Touili, T.: Permutation rewriting and algorithmic verification. Inf. Comput. 205(2), 199–224 (2007)MathSciNetCrossRef Bouajjani, A., Muscholl, A., Touili, T.: Permutation rewriting and algorithmic verification. Inf. Comput. 205(2), 199–224 (2007)MathSciNetCrossRef
6.
Zurück zum Zitat Brzozowski, J.A., Fich, F.E.: Languages of \(\mathscr {R}\)-trivial monoids. J. Comput. Syst. Sci. 20(1), 32–49 (1980)MathSciNetCrossRef Brzozowski, J.A., Fich, F.E.: Languages of \(\mathscr {R}\)-trivial monoids. J. Comput. Syst. Sci. 20(1), 32–49 (1980)MathSciNetCrossRef
7.
Zurück zum Zitat Chaubard, L., Pin, J.É., Straubing, H.: Actions, wreath products of C-varieties and concatenation product. Theor. Comput. Sci. 356(1–2), 73–89 (2006)MathSciNetCrossRef Chaubard, L., Pin, J.É., Straubing, H.: Actions, wreath products of C-varieties and concatenation product. Theor. Comput. Sci. 356(1–2), 73–89 (2006)MathSciNetCrossRef
10.
Zurück zum Zitat Guaiana, G., Restivo, A., Salemi, S.: On the trace product and some families of languages closed under partial commutations. J. Autom. Lang. Comb. 9(1), 61–79 (2004)MathSciNetMATH Guaiana, G., Restivo, A., Salemi, S.: On the trace product and some families of languages closed under partial commutations. J. Autom. Lang. Comb. 9(1), 61–79 (2004)MathSciNetMATH
11.
Zurück zum Zitat Pin, J.É.: Varieties of Formal Languages. North Oxford Academic Publishers, London (1986)CrossRef Pin, J.É.: Varieties of Formal Languages. North Oxford Academic Publishers, London (1986)CrossRef
13.
Zurück zum Zitat Pin, J.É., Straubing, H., Thérien, D.: Small varieties of finite semigroups and extensions. J. Aust. Math. Soc. 37(2), 269–281 (1984)MathSciNetCrossRef Pin, J.É., Straubing, H., Thérien, D.: Small varieties of finite semigroups and extensions. J. Aust. Math. Soc. 37(2), 269–281 (1984)MathSciNetCrossRef
14.
Zurück zum Zitat Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (2009)CrossRef Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (2009)CrossRef
15.
Zurück zum Zitat Tesson, P., Thérien, D.: Diamonds are forever: the variety DA. In: Semigroups, Algorithms, Automata and Languages, pp. 475–499. World Scientific (2002) Tesson, P., Thérien, D.: Diamonds are forever: the variety DA. In: Semigroups, Algorithms, Automata and Languages, pp. 475–499. World Scientific (2002)
Metadaten
Titel
Geometrically Closed Positive Varieties of Star-Free Languages
verfasst von
Ondřej Klíma
Peter Kostolányi
Copyright-Jahr
2020
DOI
https://doi.org/10.1007/978-3-030-40608-0_23