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:
Cellular Automata Model for Proteomics and Its Application in Cancer Immunotherapy Read chapter Read first chapter

2018 | OriginalPaper | Chapter

Self-verifying Cellular Automata

Authors : Martin Kutrib, Thomas Worsch

Published in: Cellular Automata

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

We study the computational capacity of self-verifying cellular automata with an emphasis on one-way information flow (\(\text {SVOCA}\)). A self-verifying device is a nondeterministic device where each computation path can give one of the answers yes, no, or do not know. For every input word, at least one computation path must give either the answer yes or no, and the answers given must not be contradictory. Realtime \(\text {SVOCA}\) are strictly more powerful than realtime deterministic one-way cellular automata. They can be sped-up from lineartime to realtime and are capable to simulate any lineartime computation of deterministic two-way CA. Closure and decidability properties are considered as well.

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 Fractal Arrangement for 2D Cellular Automata and Its Implementation for Outer-Totalistic Rules
next chapter CARPenter: A Cellular Automata Based Resilient Pentavalent Stream Cipher
Literature
1.
Bucher, W., Čulik II, K.: On real time and linear time cellular automata. RAIRO Inform. Théor. 18, 307–325 (1984)MathSciNetCrossRef
2.
Buchholz, T., Klein, A., Kutrib, M.: On interacting automata with limited nondeterminism. Fundam. Inform. 52, 15–38 (2002)MathSciNetMATH
3.
Buchholz, T., Kutrib, M.: On time computability of functions in one-way cellular automata. Acta Inform. 35, 329–352 (1998)MathSciNetCrossRef
4.
Choffrut, C., Čulik II, K.: On real-time cellular automata and trellis automata. Acta Inform. 21, 393–407 (1984)MathSciNetCrossRef
5.
Chomsky, N.: Context-free grammars and pushdown storage. Tech report, QPR 65, Massachusetts Institute of Technology (1962)
6.
Duriš, P., Hromkovič, J., Rolim, J.D.P., 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). https://​doi.​org/​10.​1007/​BFb0023453CrossRef
7.
8.
Fernau, H., Kutrib, M., Wendlandt, M.: Self-verifying pushdown automata. In: Freund, R., Mráz, F., Průša, D. (eds.) Non-Classical Models of Automata and Applications (NCMA 2017), vol. 329, pp. 103–117. Austrian Computer Society, Vienna (2017). books@ocg.at
9.
Fischer, P.C., Kintala, C.M.R.: Real-time computations with restricted nondeterminism. Math. Syst. Theory 12, 219–231 (1979)MathSciNetCrossRef
10.
11.
Hromkovic, J., Schnitger, G.: On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Inf. Comput. 169, 284–296 (2001)MathSciNetCrossRef
12.
Hromkovic, J., Schnitger, G.: Nondeterministic communication with a limited number of advice bits. SIAM J. Comput. 33, 43–68 (2003)MathSciNetCrossRef
13.
Ibarra, O.H., Kim, S.M., Moran, S.: Sequential machine characterizations of trellis and cellular automata and applications. SIAM J. Comput. 14, 426–447 (1985)MathSciNetCrossRef
14.
Jirásková, G., Pighizzini, G.: Optimal simulation of self-verifying automata by deterministic automata. Inf. Comput. 209, 528–535 (2011)MathSciNetCrossRef
15.
16.
17.
18.
Malcher, A.: Descriptional complexity of cellular automata and decidability questions. J. Autom. Lang. Comb. 7, 549–560 (2002)MathSciNetMATH
19.
Smith III, A.R.: Real-time language recognition by one-dimensional cellular automata. J. Comput. Syst. Sci. 6, 233–253 (1972)MathSciNetCrossRef
20.
Umeo, H., Morita, K., Sugata, K.: Deterministic one-way simulation of two-way real-time cellular automata and its related problems. Inf. Process. Lett. 14, 158–161 (1982)MathSciNetCrossRef
Metadata
Title
Self-verifying Cellular Automata
Authors
Martin Kutrib
Thomas Worsch
Copyright Year
2018
Book
Cellular Automata

Print ISBN: 978-3-319-99812-1

Electronic ISBN: 978-3-319-99813-8

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-99813-8_31

Premium Partner

    Image Credits