Skip to main content

2016 | OriginalPaper | Buchkapitel

Unrestricted State Complexity of Binary Operations on Regular Languages

verfasst von : Janusz Brzozowski

Erschienen in: Descriptional Complexity of Formal Systems

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

I study the state complexity of binary operations on regular languages over different alphabets. It is well known that if \(L'_m\) and \(L_n\) are languages restricted to be over the same alphabet, with m and n quotients, respectively, the state complexity of any binary boolean operation on \(L'_m\) and \(L_n\) is mn, and that of the product (concatenation) is \((m-1)2^n +2^{n-1}\). In contrast to this, I show that if \(L'_m\) and \(L_n\) are over their own different alphabets, the state complexity of union and symmetric difference is \(mn+m+n+1\), that of intersection is \(mn+1\), that of difference is \(mn+m+1\), and that of the product is \(m2^n+2^{n-1}\).

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!

Fußnoten
1
The atom congruence is a left congruence defined as follows: two words x and y are equivalent if \(ux\in L\) if and only if \(uy\in L\) for all \(u\in \varSigma ^*\). Thus x and y are equivalent if \(x\in u^{-1}L\) if and only if \(y\in u^{-1}L\). An equivalence class of this relation is called an atom of L [5, 7]. It follows that an atom is a non-empty intersection of complemented and uncomplemented quotients of L. The number of atoms and their quotient complexities are possible measures of complexity of regular languages [3]. For more information about atoms and their complexity, see [4, 5, 7].
 
Literatur
1.
Zurück zum Zitat Bell, J., Brzozowski, J., Moreira, N., Reis, R.: Symmetric groups and quotient complexity of boolean operations. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 1–12. Springer, Heidelberg (2014) Bell, J., Brzozowski, J., Moreira, N., Reis, R.: Symmetric groups and quotient complexity of boolean operations. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 1–12. Springer, Heidelberg (2014)
2.
Zurück zum Zitat Brzozowski, J.: Quotient complexity of regular languages. J. Autom. Lang. Comb. 15(1/2), 71–89 (2010) Brzozowski, J.: Quotient complexity of regular languages. J. Autom. Lang. Comb. 15(1/2), 71–89 (2010)
3.
4.
6.
Zurück zum Zitat Gao, Y., Salomaa, K., Yu, S.: Transition complexity of incomplete DFAs. Fund. Inform. 110, 143–158 (2011)MathSciNetMATH Gao, Y., Salomaa, K., Yu, S.: Transition complexity of incomplete DFAs. Fund. Inform. 110, 143–158 (2011)MathSciNetMATH
8.
Zurück zum Zitat Maia, E., Moreira, N., Reis, R.: Incomplete operational transition complexity of regular languages. Inform. Comput. 244, 1–22 (2015)MathSciNetCrossRefMATH Maia, E., Moreira, N., Reis, R.: Incomplete operational transition complexity of regular languages. Inform. Comput. 244, 1–22 (2015)MathSciNetCrossRefMATH
9.
Zurück zum Zitat Maslov, A.N.: Estimates of the number of states of finite automata. Dokl. Akad. Nauk SSSR 194, 1266–1268 (1970) (Russian). English translation: Soviet Math. Dokl. 11, 1373–1375 (1970) Maslov, A.N.: Estimates of the number of states of finite automata. Dokl. Akad. Nauk SSSR 194, 1266–1268 (1970) (Russian). English translation: Soviet Math. Dokl. 11, 1373–1375 (1970)
10.
11.
Zurück zum Zitat Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theoret. Comput. Sci. 125, 315–328 (1994)MathSciNetCrossRefMATH Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theoret. Comput. Sci. 125, 315–328 (1994)MathSciNetCrossRefMATH
Metadaten
Titel
Unrestricted State Complexity of Binary Operations on Regular Languages
verfasst von
Janusz Brzozowski
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-41114-9_5