Complexity-theoretic aspects of expanding cellular automata
- PDF / 718,109 Bytes
- 13 Pages / 595.276 x 790.866 pts Page_size
- 69 Downloads / 216 Views
(0123456789().,-volV)(0123456789(). ,- volV)
Complexity-theoretic aspects of expanding cellular automata Augusto Modanese1 Accepted: 9 October 2020 Ó The Author(s) 2020
Abstract The expanding cellular automata (XCA) variant of cellular automata is investigated and characterized from a complexitytheoretical standpoint. An XCA is a one-dimensional cellular automaton which can dynamically create new cells between existing ones. The respective polynomial-time complexity class is shown to coincide with ptt ðNPÞ, that is, the class of decision problems polynomial-time truth-table reducible to problems in NP. An alternative characterization based on a variant of non-deterministic Turing machines is also given. In addition, corollaries on select XCA variants are proven: XCAs with multiple accept and reject states are shown to be polynomial-time equivalent to the original XCA model. Finally, XCAs with alternative acceptance conditions are considered and classified in terms of ptt ðNPÞ and the Turing machine polynomial-time class P. Keywords Bio-inspired computing Cellular automata variants Computational complexity Varying acceptance conditions Mathematics Subject Classification 68Q05 68Q25 68Q80
1 Introduction Traditionally, cellular automata (CAs) are defined as a rigid and immutable lattice of cells; their behavior is dictated exclusively by a local transition function operating on homogeneous local configurations. This can be generalized, for instance, by mutable neighborhoods (Rosenfeld and Wu 1981) or by endowing CAs with the ability to shrink, that is, delete their cells (Rosenfeld et al. 1983). When shrinking, the automaton’s structure and dimension are preserved by ‘‘gluing’’ the severed parts and reconnecting their delimiting cells as neighbors. When employed as language recognizers, shrinking CAs (SCAs) can be more efficient than standard CAs (Rosenfeld et al. 1983; Kutrib et al. 2015).
Parts of this paper have been submitted (Modanese 2016, 2018) in partial fulfillment of the requirements for the degrees of Bachelor of Science and Master of Science at the Karlsruhe Institute of Technology (KIT). & Augusto Modanese [email protected] 1
Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany
Other variants of CAs with dynamically reconfigurable neighborhoods have emerged throughout the years. In the case of two-dimensional CAs, there is the structurally dynamical CA (SDCA) due to Ilachinski and Halpern (1987), in which the connections between neighbors are created and dropped depending on the local configuration. In the one-dimensional case, further variants in this sense are considered in the work of Dubacq (1994), where one finds, in particular, CAs whose neighborhoods vary over time. Dubacq also proposes the dynamically reconfigurable CA (DRCA), a CA whose cells are able to exchange their neighbors for neighbors of their neighbors. Dantchev (2008) later points out a drawback in the definition of DRCAs and proposes an alternative dubbed the dynamic neighborhood CA (DNCA). By relaxing the arra
Data Loading...
