Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A Snapshot of My Life Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

Cellular Automata: Descriptional Complexity and Decidability

verfasst von : Martin Kutrib, Andreas Malcher

Erschienen in: Reversibility and Universality

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We give a survey on the descriptional complexity of cellular models including one-way and two-way cellular automata, iterative arrays, and models with a fixed number of cells. For the former models so-called non-recursive trade-offs can be shown, that is, the savings in size that such automata may provide are not bounded by any recursive function. A consequence is that almost all commonly studied decidability questions are undecidable and not even semidecidable for such automata. On the other hand, for the latter models with a fixed number of cells it is possible to show recursive, in particular, polynomial bounds for mutual transformations which yield the decidability of the standard questions. Finally, we summarize results on the state complexity of the Boolean operations for one-way cellular automata and their variant with a fixed number of cells.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel A Weakly Universal Cellular Automaton on the Grid {8, 3} with Two States
Nächstes Kapitel Invertible Construction of Decimal-to-Binary Converter Using Reversible Elements
Literatur
1.
Bordihn, H., Kutrib, M., Malcher, A.: Undecidability and hierarchy results for parallel communicating finite automata. Int. J. Found. Comput. Sci. 22, 1577–1592 (2011)MathSciNetCrossRefMATH
2.
Bordihn, H., Kutrib, M., Malcher, A.: On the computational capacity of parallel communicating finite automata. Int. J. Found. Comput. Sci. 23, 713–732 (2012)MathSciNetCrossRefMATH
3.
Bordihn, H., Kutrib, M., Malcher, A.: Returning parallel communicating finite automata with communication bounds: hierarchies, decidabilities, and undecidabilities. Int. J. Found. Comput. Sci. 26, 1101–1126 (2015)MathSciNetCrossRefMATH
4.
Buchholz, T., Klein, A., Kutrib, M.: Iterative arrays with small time bounds. In: M. Nielsen, B. Rovan (eds.) Mathematical Foundations of Computer Science (MFCS 2000), LNCS, vol. 1893, pp. 243–252 (2000)
5.
Cole, S.N.: Real-time computation by \(n\)-dimensional iterative arrays of finite-state machines. IEEE Trans. Comput. C–18(4), 349–365 (1969)MathSciNetCrossRefMATH
6.
Delorme, M., Mazoyer, J. (eds.): Cellular Automata – a Parallel Model. Kluwer Academic Publishers, Dordrechtd (1999)
7.
Gao, Y., Moreira, N., Reis, R., Yu, S.: A survey on operational state complexity. J. Autom. Lang. Comb. 21(4), 251–310 (2017)MathSciNetMATH
8.
Holzer, M., Kutrib, M.: Nondeterministic finite automata - Recent results on the descriptional and computational complexity. Int. J. Found. Comput. Sci. 20, 563–580 (2009)MathSciNetCrossRefMATH
9.
Holzer, M., Kutrib, M.: Descriptional complexity – an introductory survey. In: Martín-Vide, C. (ed.) Scientific Applications of Language Methods, pp. 1–58. Imperial College Press, London (2010)
10.
Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata - A survey. Inf. Comput. 209, 456–470 (2011)MathSciNetCrossRefMATH
11.
Hopcroft, J.E., et al.: An \(n\) log \(n\) algorithm for minimizing states in a finite automaton. In: Kohavi, Z. (ed.) Theory of Machines and Computations, pp. 189–196. Academic Press, Cambridge (1971)CrossRef
12.
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Cambridge (1979)MATH
13.
Jirásková, G., Okhotin, A.: On the state complexity of operations on two-way finite automata. In: M. Ito, M. Toyama (eds.) Developments in Language Theory (DLT 2008), LNCS, vol. 5257, pp. 443–454. Springer (2008)
14.
15.
16.
Klein, A., Kutrib, M.: Cellular devices and unary languages. Fund. Inform. 78, 343–368 (2007)MathSciNetMATH
17.
Kutrib, M.: Cellular automata – a computational point of view. In: Bel-Enguix, G., Jiménez-López, M.D., Martín-Vide, C. (eds.) New Developments in Formal Languages and Applications, vol. 6, pp. 183–227. Springer, Berlin (2008)
18.
Kutrib, M.: Cellular automata and language theory. In: Meyers, R. (ed.) Encyclopedia of Complexity and System Science, pp. 800–823. Springer, Berlin (2009)
19.
Kutrib, M., Lefèvre, J., Malcher, A.: The size of one-way cellular automata. In: Fatès, N., Kari, J., Worsch, T. (eds.) AUTOMATA 2010, Discrete Mathematics and Theoretical Computer Science Proceedings, pp. 71–90. DMTCS (2010)
20.
Kutrib, M., Malcher, A.: Computations and decidability of iterative arrays with restricted communication. Parallel Process. Lett. 19, 247–264 (2009)MathSciNetCrossRef
21.
22.
Kutrib, M., Malcher, A.: The size impact of little iterative array resources. J. Cell. Autom. 7, 489–507 (2012)MathSciNetMATH
23.
Kutrib, M., Malcher, A.: Iterative arrays with set storage. J. Cell. Autom. 12, 7–26 (2017)MathSciNet
24.
Kutrib, M., Malcher, A., Wendlandt, M.: Stateless one-way multi-head finite automata with pebbles. Int. J. Found. Comput. Sci. 25, 1141–1160 (2014)MathSciNetCrossRefMATH
25.
Li, M., Vitányi, P.M.B.: An Introduction to Kolmogorov Complexity and Its Applications. Springer, Berlin (1993)CrossRefMATH
26.
Malcher, A.: Descriptional complexity of cellular automata and decidability questions. J. Autom. Lang. Comb. 7, 549–560 (2002)MathSciNetMATH
27.
Malcher, A.: On one-way cellular automata with a fixed number of cells. Fund. Inform. 58, 355–368 (2003)MathSciNetMATH
28.
Malcher, A.: Beschreibungskomplexität von Zellularautomaten. Ph.D. thesis, Institut für Informatik, Johann Wolfgang Goethe-Universität Frankfurt am Main (2004)
29.
Malcher, A.: On the descriptional complexity of iterative arrays. IEICE Trans. Inf. Syst. E87–D, 721–725 (2004)
30.
Malcher, A.: On two-way communication in cellular automata with a fixed number of cells. Theor. Comput. Sci. 330, 325–338 (2005)MathSciNetCrossRefMATH
31.
Malcher, A., Mereghetti, C., Palano, B.: Sublinearly space bounded iterative arrays. Int. J. Found. Comput. Sci. 21, 843–858 (2010)MathSciNetCrossRefMATH
32.
Martín-Vide, C., Mateescu, A., Mitrana, V.: Parallel finite automata systems communicating by states. Int. J. Found. Comput. Sci. 13, 733–749 (2002)MathSciNetCrossRefMATH
33.
Martín-Vide, C., Mitrana, V.: Some undecidable problems for parallel communicating finite automata systems. Inf. Process. Lett. 77, 239–245 (2001)MathSciNetCrossRefMATH
34.
35.
Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: Symposium on Switching and Automata Theory (SWAT 1971), pp. 188–191. IEEE (1971)
36.
37.
Nakamura, K.: Real-time language recognition by one-way and two-way cellular automata. In: M. Kutyłowski, L. Pacholski, T. Wierzbicki (eds.) Mathematical Foundations of Computer Science (MFCS 1999), LNCS, vol. 1672, pp. 220–230. Springer (1999)
38.
39.
Rozenberg, G., Bäck, T., Kok, J.N. (eds.): Handbook of Natural Computing. Springer, Berlin (2012)
40.
Seidel, S.R.: Language recognition and the synchronization of cellular automata. Tech. Rep. 79-02, Department of Computer Science, University of Iowa (1979)
41.
Smith III, A.R.: Cellular automata and formal languages. In: Symposium on Switching and Automata Theory (SWAT 1970), pp. 216–224. IEEE (1970)
42.
Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1, pp. 41–110. Springer, Berlin (1997)
43.
44.
Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theoret. Comput. Sci. 125, 315–328 (1994)MathSciNetCrossRefMATH
Metadaten
Titel
Cellular Automata: Descriptional Complexity and Decidability
verfasst von
Martin Kutrib
Andreas Malcher
Copyright-Jahr
2018
Buch
Reversibility and Universality

Print ISBN: 978-3-319-73215-2

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

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-73216-9_6