Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Unambiguity in Automata Theory Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Nondeterministic Tree Width of Regular Languages

Authors : Cezar Câmpeanu, Kai Salomaa

Published in: Descriptional Complexity of Formal Systems

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

The tree width of a nondeterministic finite automaton (NFA) counts the maximum number of computations the automaton may have on a given input. Here we consider the tree width of a regular language, which, roughly speaking, measures the amount of nondeterminism that a state-minimal NFA for the language needs. We prove that an infinite tree width is obtained from finite tree width, for most operations on regular 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 Upper Bound on Syntactic Complexity of Suffix-Free Languages
next chapter Integer Complexity: Experimental and Analytical Results II
Literature
1.
2.
Björklund, H., Martens, W.: The tractability frontier for NFA minimization. J. Comput. Syst. Sci. 78, 198–210 (2012)MATHCrossRef
3.
Brüggemann-Klein, A., Wood, D.: One-unambiguous regular languages. Inf. Comput. 142–2, 182–206 (1998)CrossRef
4.
Câmpeanu, C.: Simplyfying nondeterministic finite cover automata. Electron. Proc. Theoret. Comput. Sci. 151–AFL, 162–173 (2014)CrossRef
5.
Câmpeanu, C.: Non-deterministic finite cover automata. Sci. Ann. Comput. Sci. 29, 3–28 (2015)CrossRef
6.
7.
8.
Ellul, K.: Descriptional Complexity Measures of Regular Languages. Master’s thesis, University of Waterloo (2004)
9.
10.
11.
12.
Gruber, H., Holzer, M.: Computational complexity of NFA minimization for finite and unary languages. In: Proceedings of LATA, pp. 261–272 (2007)
13.
Holzer, M., Kutrib, M.: Nondeterministic descriptional complexity of regular languages. Int. J. Found. Comput. Sci. 14, 1087–1102 (2003)MATHMathSciNetCrossRef
14.
Hromkovič, J., Seibert, S., Karhumäki, J., Klauck, H., Schnitger, G.: Communication complexity method for measuring nondeterminism in finite automata. Inf. Comput. 172, 202–217 (2002)MATHCrossRef
15.
Jiang, T., McDowell, E., Ravikumar, B.: The structure and complexity of minimal NFAs over a unary alphabet. Int. J. Found. Comput. Sci. 2, 163–182 (1991)MATHMathSciNetCrossRef
16.
17.
Kozen, D.: Lower bounds for natural proof systems. In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, FOCS, pp. 254–266 (1977)
18.
Leung, H.: Descriptional complexity of NFA of different ambiguity. Int. J. Found. Comput. Sci. 16, 975–984 (2005)MATHCrossRef
19.
20.
Palioudakis, A., Salomaa, K., Akl, S.G.: State complexity and limited nondeterminism. In: Kutrib, M., Moreira, N., Reis, R. (eds.) DCFS 2012. LNCS, vol. 7386, pp. 252–265. Springer, Heidelberg (2012) CrossRef
21.
Palioudakis, A., Salomaa, K., Akl, S.G.: Unary NFAs with limited nondeterminism. In: Geffert, V., Preneel, B., Rovan, B., Štuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 443–454. Springer, Heidelberg (2014) CrossRef
22.
Palioudakis, A., Salomaa, K., Akl, S.G.: State complexity of finite tree width NFAs. J. Automata Lang. Comb. 17(2–4), 245–264 (2012)MATHMathSciNet
23.
Palioudakis, A.: State complexity of nondeterministic finite automata with limited nondeterminism. Ph.D. thesis, Queen’s University (2014)
24.
Ravikumar, B., Ibarra, O.H.: Relating the degree of ambiguity of finite automata to the succinctness of their representation. SIAM J. Comput. 18, 1263–1282 (1989)MATHMathSciNetCrossRef
25.
Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, Cambridge (2009) MATH
26.
Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. In: Proceedings of the 5th Symposium on Theory of Computing, pp. 1–9 (1973)
27.
Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. I, pp. 41–110. Springer, Heidelberg (1997)CrossRef
Metadata
Title
Nondeterministic Tree Width of Regular Languages
Authors
Cezar Câmpeanu
Kai Salomaa
Copyright Year
2015
Book
Descriptional Complexity of Formal Systems

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

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

Copyright Year: 2015

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

Premium Partner

    Image Credits