Top

Published in:

2019 | OriginalPaper | Chapter

The Range of State Complexities of Languages Resulting from the Cut Operation

Authors : Markus Holzer, Michal Hospodár

Published in: Language and Automata Theory and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We investigate the state complexity of languages resulting from the cut operation of two regular languages represented by minimal deterministic finite automata with m and n states. We show that the entire range of complexities, up to the known upper bound, can be produced in the case when the input alphabet has at least two symbols. Moreover, we prove that in the unary case, only complexities up to \(2m-1\) and between n and \(m+n-2\) can be produced, while if \(2m\le n-1\), then the complexities from 2m up to \(n-1\) cannot be produced.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Closure and Nonclosure Properties of the Compressible and Rankable Sets

next chapter State Complexity of Pseudocatenation

Berglund, M., Björklund, H., Drewes, F., van der Merwe, B., Watson, B.: Cuts in regular expressions. In: Béal, M.-P., Carton, O. (eds.) DLT 2013. LNCS, vol. 7907, pp. 70–81. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38771-5_8CrossRefMATH

Čevorová, K.: Kleene star on unary regular languages. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol. 8031, pp. 277–288. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39310-5_26CrossRef

Čevorová, K., Jirásková, G., Krajňáková, I.: On the square of regular languages. In: Holzer, M., Kutrib, M. (eds.) CIAA 2014. LNCS, vol. 8587, pp. 136–147. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08846-4_10CrossRefMATH

Drewes, F., Holzer, M., Jakobi, S., van der Merwe, B.: Tight bounds for cut-operations on deterministic finite automata. Fundam. Inform. 155(1–2), 89–110 (2017)MathSciNetCrossRef

Geffert, V.: Magic numbers in the state hierarchy of finite automata. Inf. Comput. 205(11), 1652–1670 (2007)MathSciNetCrossRef

Geffert, V.: State hierarchy for one-way finite automata. J. Autom. Lang. Comb. 12(1–2), 139–145 (2007)MathSciNetMATH

Harrison, M.A.: Introduction to Formal Language Theory. Addison-Wesley, Boston (1978)MATH

Hricko, M., Jirásková, G., Szabari, A.: Union and intersection of regular languages and descriptional complexity. In: DCFS 2005, pp. 170–181. Università degli Studi di Milano, Italy (2005)

Iwama, K., Kambayashi, Y., Takaki, K.: Tight bounds on the number of states of DFAs that are equivalent to n-state NFAs. Theoret. Comput. Sci. 237(1–2), 485–494 (2000)MathSciNetCrossRef

10.

Iwama, K., Matsuura, A., Paterson, M.: A family of NFA’s which need \(2^n-\alpha \) deterministic states. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol. 1893, pp. 436–445. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44612-5_39CrossRefMATH

11.

Jirásek, J., Jirásková, G., Szabari, A.: Deterministic blow-ups of minimal nondeterministic finite automata over a fixed alphabet. Internat. J. Found. Comput. Sci. 19(3), 617–631 (2008)MathSciNetCrossRef

12.

Jirásková, G.: Deterministic blow-ups of minimal NFA’s. RAIRO-ITA 40(3), 485–499 (2006)MathSciNetMATH

13.

Jirásková, G.: Concatenation of regular languages and descriptional complexity. Theory Comput. Syst. 49(2), 306–318 (2011)MathSciNetCrossRef

14.

Jirásková, G.: Magic numbers and ternary alphabet. Int. J. Found. Comput. Sci. 22(2), 331–344 (2011)MathSciNetCrossRef

15.

Jirásková, G., Palmovský, M., Šebej, J.: Kleene closure on regular and prefix-free languages. In: Holzer, M., Kutrib, M. (eds.) CIAA 2014. LNCS, vol. 8587, pp. 226–237. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08846-4_17CrossRefMATH

16.

Jirásková, G., Szabari, A., Šebej, J.: The complexity of languages resulting from the concatenation operation. In: Câmpeanu, C., Manea, F., Shallit, J. (eds.) DCFS 2016. LNCS, vol. 9777, pp. 153–167. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-41114-9_12CrossRefMATH

17.

Lupanov, O.B.: A comparison of two types of finite automata. Problemy Kibernetiki 9, 321–326 (1963). (in Russian). German translation: Über den Vergleich zweier Typen endlicher Quellen. Probleme der Kybernetik 6, 328–335 (1966)

18.

Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: Proceedings of the 12th Annual Symposium on Switching and Automata Theory, pp. 188–191. IEEE Computer Society Press (1971)

19.

Moore, F.R.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Trans. Comput. C–20, 1211–1219 (1971)CrossRef

20.

Nicaud, C.: Average state complexity of operations on unary automata. In: Kutyłowski, M., Pacholski, L., Wierzbicki, T. (eds.) MFCS 1999. LNCS, vol. 1672, pp. 231–240. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48340-3_21CrossRefMATH

21.

Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3, 114–125 (1959)MathSciNetCrossRef

22.

Šebej, J.: Reversal on regular languages and descriptional complexity. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol. 8031, pp. 265–276. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39310-5_25CrossRefMATH

23.

Yershov, Y.L.: On a conjecture of V. A. Uspenskii. Algebra i logika 1, 45–48 (1962). (in Russian)MathSciNet

24.

Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theoret. Comput. Sci. 125(2), 315–328 (1994)MathSciNetCrossRef

Title: The Range of State Complexities of Languages Resulting from the Cut Operation
Authors: Markus Holzer
Michal Hospodár
Publisher: Springer International Publishing
Book: Language and Automata Theory and Applications
Print ISBN: 978-3-030-13434-1

Electronic ISBN: 978-3-030-13435-8

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-13435-8_14

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner