Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Theory of Computing Systems
Erschienen in: Theory of Computing Systems 4/2019

09.05.2018

Generic Results for Concatenation Hierarchies

verfasst von: Thomas Place, Marc Zeitoun

Erschienen in: Theory of Computing Systems | Ausgabe 4/2019

Einloggen

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

search-config
loading …

Abstract

In the theory of formal languages, the understanding of concatenation hierarchies of regular languages is one of the most fundamental and challenging topics. In this paper, we survey progress made on this problem since 1971. We also establish new generic statements regarding this problem.
Vorheriger Artikel On Algorithmic Statistics for Space-bounded Algorithms
Nächster Artikel The Descriptive Complexity of Subgraph Isomorphism Without Numerics

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Fußnoten
1
In fact, the original formulation of Pin and Straubing considers level 2 in the Straubing-Thérien hierarchy and not level \(\frac {3}{2}\).
 
Literatur
1.
Almeida, J.: Some algorithmic problems for Pseudovarieties. Publicationes Mathematicae Debrecen 54, 531–552 (1999). Proceedings of Automata and Formal Languages, VIIIMathSciNetMATH
2.
Arfi, M.: Polynomial operations on rational languages. In: STACS’87, Lect. Notes Comp. Sci., pp. 198–206. Springer (1987)
3.
4.
Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata, volume 129 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2009)
5.
Bojańczyk, M.: Star height via games. In: LICS’15, pp. 214–219. IEEE Computer Society (2015)
6.
Branco, M., Pin, J.-É.: Equations defining the polynomial closure of a lattice of regular languages. In: ICALP 2009, volume 5556 of Lect. Notes Comp. Sci., pp. 115–126. Springer (2009)
7.
Brzozowski, J.A.: Developments in the theory of regular languages. In: IFIP Congress, pp. 29–40 (1980)
8.
Brzozowski, J.A.: Open problems about regular languages. In: Book, R.V. (ed.) Formal Language Theory, pp. 23–47. Academic Press (1980)
9.
10.
Brzozowski, J.A., Knast, R.: The dot-depth hierarchy of star-free languages is infinite. J. Comput. Syst. Sci. 16(1), 37–55 (1978)MathSciNetCrossRefMATH
11.
Colcombet, T.: Factorization forests for infinite words and applications to countable scattered linear orderings. Theor. Comput. Sci. 411(4-5), 751–764 (2010)MathSciNetCrossRefMATH
12.
13.
14.
15.
16.
17.
18.
Kleene, S.C.: Representation of events in nerve nets and finite automata. In: Shannon, C., McCarthy, J. (eds.) Annals of Mathematics Studies 34, pp. 3–41. Princeton University Press (1956)
19.
20.
Kufleitner, M.: The height of factorization forests. In: Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS’08, pp. 443–454 (2008)
21.
McNaughton, R., Papert, S.A.: Counter-Free Automata. MIT Press, Cambridge (1971)MATH
22.
23.
24.
Pin, J.-É.: A variety theorem without complementation. Russian mathem. (Iz. VUZ) 39, 74–83 (1995)
25.
Pin, J.-É.: An explicit formula for the intersection of two polynomials of regular languages. In: DLT 2013, Volume 7907 of Lect. Notes Comp. Sci., pp. 31–45. Springer (2013)
26.
Pin, J.-E.́: Mathematical Foundations of Automata Theory. In preparation (2016)
27.
Pin, J.-É.: Open Problems About Regular Languages, 35 Years Later. World Scientific (2017)
28.
Pin, J.-É., Straubing, H.: Monoids of upper triangular boolean matrices. In: Semigroups. Structure and Universal Algebraic Problems, vol. 39, pp. 259–272. North-Holland (1985)
29.
Pin, J.-É., Weil, P.: Polynomial closure and unambiguous product. In: ICALP’95, Lect. Notes Comp. Sci., pp. 348–359. Springer (1995)
30.
31.
32.
Place, T.: Separating regular languages with two quantifier alternations. In: LICS’15, pp. 202–213 (2015)
33.
Place, T.: Separating regular languages with two quantifiers alternations. To appear. For a preliminary version see arXiv:1707.​03295 (2018)
34.
Place, T., Zeitoun, M.: Going higher in the first-order quantifier alternation hierarchy on words. In: ICALP’14, Lect. Notes Comp. Sci., pp. 342–353. Springer (2014)
35.
Place, T., Zeitoun, M.: Separation and the successor relation. In: STACS’15, pp. 662–675. Leibniz-Zentrum fuer Informatik, Lipics (2015)
36.
Place, T., Zeitoun, M.: The covering problem: a unified approach for investigating the expressive power of logics. In: MFCS’16, pp. 77:1–77:15. Leibniz-Zentrum fuer Informatik, Lipics (2016)
37.
Place, T., Zeitoun, M.: Adding successor: a transfer theorem for separation and covering. arXiv:1709.​10052 (2017)
38.
Place, T., Zeitoun, M.: Concatenation hierarchies: new bottle, old wine. In: Weil, P. (ed.) CSR 2017, volume 10304 of Lect. Notes Comp. Sci., pp. 25–37. Springer (2017)
39.
40.
Place, T., Zeitoun, M.: Going higher in first-order quantifier alternation hierarchies on words. arXiv:1707.​05696 (2017)
41.
Place, T., Zeitoun, M.: Separation for dot-depth two. In: LICS 2017, pp. 1–12. IEEE Computer Society (2017)
42.
Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (2009)CrossRefMATH
43.
44.
Simon, I.: Hierarchies of events of dot-depth one (1972)
45.
Simon, I.: Piecewise testable events. In: Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, pp. 214–222. Springer (1975)
46.
47.
48.
Straubing, H.: A generalization of the Schützenberger product of finite monoids. Theoret. Comp. Sci. 13(2), 137–150 (1981)MathSciNetCrossRefMATH
49.
50.
51.
Thérien, D.: The power of diversity. In: Holzer, M., Kutrib, M., Pighizzini, G. (eds.) Descriptional Complexity of Formal Systems, volume 6808 of Lect. Notes Comp. Sci., pp. 43–54. Springer (2011)
52.
53.
Thomas, W.: An application of the Ehrenfeucht-Fraïssé game in formal language theory. Mémoires de la Société Mathématique de France 16, 11–21 (1984)CrossRefMATH
54.
Thomas, W.: A Concatenation game and the dot-depth hierarchy. In: Computation Theory and Logic, pp. 415–426. Springer, Berlin (1987)
Metadaten
Titel
Generic Results for Concatenation Hierarchies
verfasst von
Thomas Place
Marc Zeitoun
Publikationsdatum
09.05.2018
Verlag
Springer US
Erschienen in
Theory of Computing Systems / Ausgabe 4/2019
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-018-9867-0

Weitere Artikel der Ausgabe 4/2019

Theory of Computing Systems 4/2019 Zur Ausgabe

OriginalPaper

On Algorithmic Statistics for Space-bounded Algorithms

OriginalPaper

Green’s Relations in Deterministic Finite Automata

OriginalPaper

An Adequacy Theorem for Dependent Type Theory

OriginalPaper

Cascade Heap: Towards Time-Optimal Extractions

OriginalPaper

Verification of Quantum Computation: An Overview of Existing Approaches

OriginalPaper

Unary Coded PSPACE-Complete Languages in ASPACE(loglog n)

Premium Partner

    Bildnachweise