Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures

From MaRDI portal

Publication:2561573

Jump to:navigation, search

DOI10.1016/S0022-0000(72)80013-8zbMath0263.94019OpenAlexW2000451777WikidataQ55921397 ScholiaQ55921397MaRDI QIDQ2561573

Yale N. Patt, Serafino Amoroso

Publication date: 1972

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(72)80013-8

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (only showing first 100 items - show all)

A survey of cellular automata: types, dynamics, non-uniformity and applications ⋮ Characterization of reversible intermediate boundary cellular automata ⋮ \(m\)-asynchronous cellular automata: from fairness to quasi-fairness ⋮ Group structured linear cellular automata over \(Z_ m\) ⋮ Efficient exhaustive listings of reversible one dimensional cellular automata ⋮ On the size of the inverse neighborhoods for one-dimensional reversible cellular automata ⋮ On ergodic linear cellular automata over Zm ⋮ Intrinsic universality of a 1-dimensional reversible Cellular Automaton ⋮ Inversion of 2D cellular automata: Some complexity results ⋮ Predecessors of cellular automata states. II: Pre-images of finite sequences ⋮ Rice's theorem for the limit sets of cellular automata ⋮ The surjectivity problem for 2D cellular automata ⋮ A tight linear bound on the synchronization delay of bijective automata ⋮ Growing patterns in 1D cellular automata ⋮ Real-time reversible iterative arrays ⋮ A Characterization of Cellular Automata Generated by Idempotents on the Full Shift ⋮ (Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata ⋮ Inverse rules of ECA with rule number 150 ⋮ On the dynamics of cellular automata induced from a prefix code ⋮ UNCONVENTIONAL INVERTIBLE BEHAVIORS IN REVERSIBLE ONE-DIMENSIONAL CELLULAR AUTOMATA ⋮ Asynchrony Immune Cellular Automata ⋮ Ternary reversible number-conserving cellular automata are trivial ⋮ Reversibility problem of multidimensional finite cellular automata ⋮ Modeling and optimization for networked evolutionary games with player exit mechanism: semi-tensor product of matrices method ⋮ Classes of Languages Generated by the Kleene Star of a Word ⋮ Cellular automata between sofic tree shifts ⋮ Local rule distributions, language complexity and non-uniform cellular automata ⋮ An interconnection of local maps inducing onto global maps ⋮ On computing the entropy of cellular automata. ⋮ Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage ⋮ On Radius 1 Nontrivial Reversible and Number-Conserving Cellular Automata ⋮ On the Reversibility of ECAs with Fully Asynchronous Updating: The Recurrence Point of View ⋮ On the conjugacy problem of cellular automata ⋮ On time-symmetry in cellular automata ⋮ Pattern decomposition for tessellation automata ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ Decidable Properties of 2D Cellular Automata ⋮ Reversible computing and cellular automata -- a survey ⋮ ON A CHARACTERIZATION OF CELLULAR AUTOMATA IN TILINGS OF THE HYPERBOLIC PLANE ⋮ Structure of the invertible CA transformations group ⋮ Three research directions in non-uniform cellular automata ⋮ Distributed Multi-authority Attribute-Based Encryption Using Cellular Automata ⋮ The structure of reversible one-dimensional cellular automata ⋮ A two-layer representation of four-state reversible number-conserving 2D cellular automata ⋮ Hybrid one-dimensional reversible cellular automata are regular ⋮ A Random NP-complete problem for inversion of 2D cellular automata ⋮ Characterization of sets of limit measures of a cellular automaton iterated on a random configuration ⋮ Fast reversible language recognition using cellular automata ⋮ Nondeterministic cellular automata ⋮ SPECTRAL PROPERTIES OF REVERSIBLE ONE-DIMENSIONAL CELLULAR AUTOMATA ⋮ Reversibility of general 1D linear cellular automata over the binary field \(\mathbb{Z}_2\) under null boundary conditions ⋮ Towards a neighborhood simplification of tile systems: from Moore to quasi-linear dependencies ⋮ A closed formula for the inverse of a reversible cellular automaton with \((2 R + 1)\)-cyclic rule ⋮ Survey of research in the theory of homogeneous structures and their applications ⋮ Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata ⋮ Bulking II: Classifications of cellular automata ⋮ Permutive one-way cellular automata and the finiteness problem for automaton groups ⋮ Indecomposable local maps of tessellation automata ⋮ Procedures for calculating reversible one-dimensional cellular automata ⋮ On reversibility in cellular automata ⋮ The behavioral properties of homogeneous structures ⋮ Theory of cellular automata: a survey ⋮ On the structure of the set of reversible cellular automata ⋮ On ergodic one-dimensional cellular automata ⋮ Topological and measure-theoretic properties of one-dimensional cellular automata ⋮ The vector string descriptor as a tool in the analysis of cellular automata systems ⋮ Computation and construction universality of reversible cellular automata ⋮ Certain relations between properties of maps of tessellation automata ⋮ Local maps inducing surjective global maps of one-dimensional tessellation automata ⋮ A Cryptosystem Based on the Composition of Reversible Cellular Automata ⋮ (A-)synchronous (non)-deterministic cell spaces simulating each other ⋮ When-and how-can a cellular automaton be rewritten as a lattice gas? ⋮ Characterization of 1-d Periodic Boundary Reversible CA ⋮ Decidability for some problems of linear cellular automata over finite commutative rings ⋮ On the complexity of asynchronous freezing cellular automata ⋮ Invertible linear cellular automata over \(\mathbb{Z}_m\): Algorithmic and dynamical aspects ⋮ Pre-expansivity in cellular automata ⋮ PERIODIC CONFIGURATIONS OF SUBSHIFTS ON GROUPS ⋮ Lyapunov exponent versus expansivity and sensitivity in cellular automata ⋮ The constructibility of a configuration in a cellular automaton ⋮ ON THE REVERSIBILITY OF 150 WOLFRAM CELLULAR AUTOMATA ⋮ Surprising Areas in the Quest for Small Universal Devices ⋮ Reversibility of non-saturated linear cellular automata on finite triangular grids ⋮ Some applications of propositional logic to cellular automata ⋮ ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS ⋮ Reversibility of number-conserving 1D cellular automata: unlocking insights into the dynamics for larger state sets ⋮ Ergodicity, transitivity, and regularity for linear cellular automata over \(\mathbb{Z}_m\) ⋮ Nonconstructible blocks in 1D cellular automata: minimal generators and natural systems ⋮ Recursive paths in cross-connected trees and an application to cell spaces ⋮ Real-Time Reversible One-Way Cellular Automata ⋮ Graph-theoretical characterization of invertible cellular automata ⋮ Reversible space-time simulation of cellular automata ⋮ CELLULAR AUTOMATA OVER SEMI-DIRECT PRODUCT GROUPS: REDUCTION AND INVERTIBILITY RESULTS ⋮ Linear cellular automata over \(Z_ m\) ⋮ Decidability and undecidability in cellular automata ⋮ Computation in reversible cellular automata ⋮ Computation theoretic aspects of cellular automata ⋮ Reversibility of 2D cellular automata is undecidable ⋮ Classifying circular cellular automata ⋮ Invertible cellular automata: A review

Cites Work

This page was built for publication: Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:2561573&oldid=15313249"