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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Unambiguity in Automata Theory Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Square on Ideal, Closed and Free Languages

verfasst von : Kristína Čevorová

Erschienen in: Descriptional Complexity of Formal Systems

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We study the deterministic state complexity of a language accepted by an \(n\)-state DFA concatenated with itself for languages from certain subregular classes. Tight upper bounds are obtained on optimal alphabets for prefix-closed, xsided-ideal and xfix-free languages, except for suffix-free, where a ternary alphabet is used.

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

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
Vorheriges Kapitel Integer Complexity: Experimental and Analytical Results II
Nächstes Kapitel A Tentative Approach for the Wadge-Wagner Hierarchy of Regular Tree Languages of Index [0, 2]
Literatur
1.
Brzozowski, J.A., Jirásková, G., Li, B.: Quotient complexity of ideal languages. Theor. Comput. Sci. 470, 36–52 (2013)MATHCrossRef
2.
Brzozowski, J.A., Jirásková, G., Li, B., Smith, J.: Quotient complexity of bifix-, factor-, and subword-free regular languages. In: Dömösi, P., Iván, S. (eds.) AFL, pp. 123–137 (2011)
3.
Brzozowski, J.A., Jirásková, G., Zou, C.: Quotient complexity of closed languages. Theor. Comp. Sys. 54(2), 277–292 (2014)CrossRef
4.
5.
Bordihn, H., Holzer, M., Kutrib, M.: Determination of finite automata accepting subregular languages. Theor. Comput. Sci. 410(35), 3209–3222 (2009). DCFS proceedingsMATHMathSciNetCrossRef
6.
Brzozowski, J., Ye, Y.: Syntactic complexity of ideal and closed languages. In: Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol. 6795, pp. 117–128. Springer, Heidelberg (2011) CrossRef
7.
Cmorik, R., Jirásková, G.: Basic operations on binary suffix-free languages. In: Kotásek, Z., Bouda, J., Černá, I., Sekanina, L., Vojnar, T., Antoš, D. (eds.) MEMICS 2011. LNCS, vol. 7119, pp. 94–102. Springer, Heidelberg (2012) CrossRef
8.
Jirásková, G., Krausová, M.: Complexity in prefix-free regular languages. In: McQuillan, I., Pighizzini, G. (eds.) DCFS. EPTCS, vol. 31, pp. 197–204 (2010)
9.
Kao, J.Y., Rampersad, N., Shallit, J.: On NFAs where all states are final, initial, or both. Theor. Comput. Sci. 410(4749), 5010–5021 (2009)MATHMathSciNetCrossRef
10.
Čevorová, K., Jirásková, G., Mlynárčik, P., Palmovský, M., Šebej, J.: Operations on automata with all states final. In: Ésik, Z., Fülöp, Z. (eds.) Proceedings 14th International Conference on Automata and Formal Languages, AFL 2014, Szeged, Hungary, May 27–29, 2014. EPTCS, vol. 151, pp. 201–215 (2014)
11.
Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company, Boston (1997) MATH
12.
Han, Y.S., Salomaa, K., Wood, D.: State complexity of prefix-free regular languages. In: Descriptional Complexity of Formal Systems, pp. 165–176 (2006)
13.
Han, Y.-S., Salomaa, K.: State complexity of basic operations on suffix-free regular languages. In: Kučera, L., Kučera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 501–512. Springer, Heidelberg (2007) CrossRef
14.
Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theor. Comput. Sci. 125(2), 315–328 (1994)MATHMathSciNetCrossRef
Metadaten
Titel
Square on Ideal, Closed and Free Languages
verfasst von
Kristína Čevorová
Copyright-Jahr
2015
Buch
Descriptional Complexity of Formal Systems

Print ISBN: 978-3-319-19224-6

Electronic ISBN: 978-3-319-19225-3

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-19225-3_6