Top

Published in:

2016 | OriginalPaper | Chapter

Descriptional Complexity of Bounded Regular Languages

Authors : Andrea Herrmann, Martin Kutrib, Andreas Malcher, Matthias Wendlandt

Published in: Descriptional Complexity of Formal Systems

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 descriptional complexity of the subregular language classes of (strongly) bounded regular languages. In the first part, we study the costs for the determinization of nondeterministic finite automata accepting strongly bounded regular languages. The upper bound for the costs is larger than the costs for determinizing unary regular languages, but lower than the costs for determinizing arbitrary regular languages. In the second part, we study for (strongly) bounded languages the deterministic operational state complexity of the Boolean operations as well as the operations reversal, concatenation, and iteration. In detail, we present upper and lower bounds and we develop for the proof of the lower bounds a tool that exploits the number of different colorings of cycles occurring in deterministic finite automata accepting bounded languages.

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 Operations on Weakly Recognizing Morphisms

next chapter The Complexity of Languages Resulting from the Concatenation Operation

Birget, J.C.: Intersection and union of regular languages and state complexity. Inform. Process. Lett. 43, 185–190 (1992)MathSciNetCrossRefMATH

Bordihn, H., Holzer, M., Kutrib, M.: Determination of finite automata accepting subregular languages. Theor. Comput. Sci. 410(35), 3209–3222 (2009)MathSciNetCrossRefMATH

Chrobak, M.: Finite automata and unary languages. Theoret. Comput. Sci. 47(2), 149–158 (1986)MathSciNetCrossRefMATH

Chrobak, M.: Errata to “Finite automata and unary languages”. Theoret. Comput. Sci. 302, 497–498 (2003)MathSciNetCrossRef

Erickson, M.J.: Introduction to Combinatorics. Wiley, New York (1996)CrossRefMATH

Gao, Y., Moreira, N., Reis, R., Yu, S.: A survey on operational state complexity. CoRR abs/1509.03254 (2015). http://arxiv.org/abs/1509.03254

Ginsburg, S., Spanier, E.H.: Bounded regular sets. Proc. Amer. Math. Soc. 17(5), 1043–1049 (1966)MathSciNetCrossRefMATH

Ginsburg, S.: The Mathematical Theory of Context-Free Languages. McGraw Hill, New York (1966)MATH

Glaister, I., Shallit, J.: A lower bound technique for the size of nondeterministic finite automata. Inform. Process. Lett. 59, 75–77 (1996)MathSciNetCrossRefMATH

10.

Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)MATH

11.

Ibarra, O.H.: Reversal-bounded multicounter machines and their decision problems. J. ACM 25(1), 116–133 (1978)MathSciNetCrossRefMATH

12.

Ibarra, O.H., Ravikumar, B.: On bounded languages and reversal-bounded automata. Inf. Comput. 246, 30–42 (2016)MathSciNetCrossRefMATH

13.

Ibarra, O.H., Seki, S.: Characterizations of bounded semilinear languages by one-way and two-way deterministic machines. Int. J. Found. Comput. Sci. 23(6), 1291–1306 (2012)MathSciNetCrossRefMATH

14.

Leiss, E.L.: Succinct representation of regular languages by Boolean automata. Theoret. Comput. Sci. 13, 323–330 (1981)MathSciNetCrossRefMATH

15.

Malcher, A., Pighizzini, G.: Descriptional complexity of bounded context-free languages. Inf. Comput. 227, 1–20 (2013)MathSciNetCrossRefMATH

16.

Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: SWAT 1971, pp. 188–191. IEEE (1971)

17.

Pighizzini, G., Shallit, J.: Unary language operations, state complexity and Jacobsthal’s function. Int. J. Found. Comput. Sci. 13, 145–159 (2002)MathSciNetCrossRefMATH

18.

Salomaa, K., Yu, S.: NFA to DFA transformation for finite languages over arbitrary alphabets. J. Autom. Lang. Comb. 2, 177–186 (1997)MathSciNetMATH

19.

Valiant, L.G.: Regularity and related problems for deterministic pushdown automata. J. ACM 22, 1–10 (1975)MathSciNetCrossRefMATH

20.

Yu, S.: State complexity of regular languages. J. Autom. Lang. Comb. 6, 221–234 (2001)MathSciNetMATH

21.

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

Title: Descriptional Complexity of Bounded Regular Languages
Authors: Andrea Herrmann
Martin Kutrib
Andreas Malcher
Matthias Wendlandt
Publisher: Springer International Publishing
Book: Descriptional Complexity of Formal Systems
Print ISBN: 978-3-319-41113-2

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

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-41114-9_11

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