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
Erschienen in:
Completely Reachable Automata Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

State Complexity of Prefix Distance of Subregular Languages

verfasst von : Timothy Ng, David Rappaport, Kai Salomaa

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

The neighbourhood of a regular language of constant radius with respect to the prefix distance is always regular. We give upper bounds and matching lower bounds for the size of the minimal deterministic finite automaton (DFA) needed for the radius k prefix distance neighbourhood of an n state DFA that recognizes, respectively, a finite, a prefix-closed and a prefix-free language. For prefix-closed languages the lower bound automata are defined over a binary alphabet. For finite and prefix-free regular languages the lower bound constructions use an alphabet that depends on the size of the DFA and it is shown that the size of the alphabet is optimal.

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 Unary Self-verifying Symmetric Difference Automata
Nächstes Kapitel Two Results on Discontinuous Input Processing
Literatur
1.
Bordihn, H., Holzer, M., Kutrib, M.: Determination of finite automata accepting subregular languages. Theor. Comput. Sci. 410(35), 3209–3222 (2009)MathSciNetCrossRefMATH
2.
Calude, C.S., Salomaa, K., Yu, S.: Additive distances and quasi-distances between words. J. Univ. Comput. Sci. 8(2), 141–152 (2002)MathSciNetMATH
3.
Câmpeanu, C., Culik II, K., Salomaa, K., Yu, S.: State complexity of basic operations on finite languages. In: Boldt, O., Jürgensen, H. (eds.) WIA 1999. LNCS, vol. 2214, p. 60. Springer, Heidelberg (2001)CrossRef
4.
Choffrut, C., Pighizzini, G.: Distances between languages and reflexivity of relations. Theor. Comput. Sci. 286(1), 117–138 (2002)MathSciNetCrossRefMATH
5.
6.
7.
Han, Y.S., Salomaa, K., Wood, D.: State complexity of prefix-free regular languages. In: Proceedings of the 8th International Workshop on Descriptive Complexity of Formal Systems. pp. 165–176 (2006)
8.
Holzer, M., Jakobi, S., Kutrib, M.: The magic number problem for subregular language families. Int. J. Found. Comput. Sci. 23(1), 115–131 (2012)MathSciNetCrossRefMATH
9.
Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata – a survey. Inform. Comput. 209, 456–470 (2011)MathSciNetCrossRefMATH
10.
Holzer, M., Kutrib, M., Meckel, K.: Nondeterministic state complexity of star-free languages. In: Bouchou-Markhoff, B., Caron, P., Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2011. LNCS, vol. 6807, pp. 178–189. Springer, Heidelberg (2011)CrossRef
11.
Holzer, M., Truthe, B.: On relations between some subregular language families. Proc. NCMA 2015, 109–124 (2015)
12.
Kao, J.Y., Rampersad, N., Shallit, J.: On NFAs where all states are final, initial, or both. Theor. Comput. Sci. 410(47–49), 5010–5021 (2009)MathSciNetCrossRefMATH
13.
Kutrib, M., Pighizzini, G.: Recent trends in descriptional complexity of formal languages. Bull. EATCS 111, 70–86 (2013)MathSciNet
14.
Ng, T., Rappaport, D., Salomaa, K.: State complexity of prefix distance. In: Drewes, F. (ed.) CIAA 2015. LNCS, vol. 9223, pp. 238–249. Springer, Heidelberg (2015)CrossRef
15.
Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, Cambridge (2009)MATH
16.
Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 41–110. Springer, Heidelberg (1997)CrossRef
Metadaten
Titel
State Complexity of Prefix Distance of Subregular Languages
verfasst von
Timothy Ng
David Rappaport
Kai Salomaa
Copyright-Jahr
2016
Buch
Descriptional Complexity of Formal Systems

Print ISBN: 978-3-319-41113-2

Electronic ISBN: 978-3-319-41114-9

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-41114-9_15

Premium Partner

    Bildnachweise