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:
Completely Reachable Automata Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Self-Verifying Finite Automata and Descriptional Complexity

Author : Galina Jirásková

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

We survey recent results on the descriptional complexity of self-verifying finite automata. In particular, we discuss the cost of simulation of self-verifying finite automata by deterministic finite automata, and the complexity of basic regular operations on languages represented by self-verifying finite automata.

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 Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems
next chapter On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection
Literature
1.
Assent, I., Seibert, S.: An upper bound for transforming self-verifying automata into deterministic ones. Theor. Inf. Appl. 41, 261–265 (2007)MathSciNetCrossRefMATH
2.
Birget, J.C.: Partial orders on words, minimal elements of regular languages, and state complexity. Theoret. Comput. Sci. 119, 267–291 (1993)MathSciNetCrossRefMATH
3.
Brzozowski, J.A.: Quotient complexity of regular languages. J. Autom. Lang. Comb. 15, 71–89 (2010)
4.
Ďuriš, P., Hromkovič, J., Rolim, J., Schnitger, G.: Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, pp. 117–128. Springer, Heidelberg (1997)CrossRef
5.
Ershov, U.L.: On a conjecture of W.U. Uspenskii. Algebra i Logika (Seminar) 1, 45–48 (1962). (in Russian)
6.
Glaister, I., Shallit, J.: A lower bound technique for the size of nondeterministic finite automata. Inf. Process. Lett. 59, 75–77 (1996)MathSciNetCrossRefMATH
7.
Holzer, M., Kutrib, M.: Nondeterministic descriptional complexity of regular languages. Int. J. Found. Comput. Sci. 14, 1087–1102 (2003)MathSciNetCrossRefMATH
8.
Hromkovič, J., Schnitger, G.: On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Inf. Comput. 169, 284–296 (2001)MathSciNetCrossRefMATH
9.
Jirásek, J.Š., Jirásková, G., Szabari, A.: Operations on self-verifying finite automata. In: Beklemishev, L.D. (ed.) CSR 2015. LNCS, vol. 9139, pp. 231–261. Springer, Heidelberg (2015)
10.
11.
Jirásková, G., Pighizzini, G.: Optimal simulation of self-verifying automata by deterministic automata. Inf. Comput. 209, 528–535 (2011)MathSciNetCrossRefMATH
12.
13.
14.
Lupanov, O.B.: A comparison of two types of finite automata. Problemy Kibernetiki 9, 321–326 (1963). (in Russian)
15.
Maslov, A.N.: Estimates of the number of states of finite automata. Soviet Math. Doklady 11, 1373–1375 (1970)MATH
16.
17.
18.
Moore, F.: 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–1214 (1971)CrossRefMATH
19.
20.
Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two-way finite automata. In: Proceedings of the 10th Annual ACM STOC, pp. 275–286 (1978)
21.
Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company, Boston (1997)MATH
22.
Yu, S.: Chapter 2: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. I, pp. 41–110. Springer, Heidelberg (1997)
23.
Yu, S., Zhuang, Q., Salomaa, K.: The state complexity of some basic operations on regular languages. Theoret. Comput. Sci. 125, 315–328 (1994)MathSciNetCrossRefMATH
24.
Č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)CrossRef
Metadata
Title
Self-Verifying Finite Automata and Descriptional Complexity
Author
Galina Jirásková
Copyright Year
2016
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_3

Premium Partner

    Image Credits