Reversal-Bounded Multicounter Machines and Their Decision Problems

DOI10.1145/322047.322058zbMath0365.68059OpenAlexW2023999667MaRDI QIDQ4140393

Publication date: 1978

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322047.322058

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Turing machines and related notions (03D10)

Related Items (max. 100)

Lossiness of communication channels modeled by transducers1 ⋮ Multitape NFA: Weak Synchronization of the Input Heads ⋮ Verification of Gap-Order Constraint Abstractions of Counter Systems ⋮ Model-checking CTL* over flat Presburger counter systems ⋮ The Complexity of Reversal-Bounded Model-Checking ⋮ On the Density of Context-Free and Counter Languages ⋮ Multi-sequential Word Relations ⋮ SCHEMA FOR PARALLEL INSERTION AND DELETION: REVISITED ⋮ Equivalence between model-checking flat counter systems and Presburger arithmetic ⋮ Automata with Modulo Counters and Nondeterministic Counter Bounds ⋮ Quantifying Communication in Synchronized Languages ⋮ Hierarchies and Characterizations of Stateless Multicounter Machines ⋮ Solvable problems for transformers with reversal-bounded counters ⋮ On the decidability of the valuedness problem for two-way finite transducers ⋮ Security of Numerical Sensors in Automata ⋮ On two-way weak counter machines ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ On the complexity of decision problems for some classes of machines and applications ⋮ On the existential arithmetics with addition and bitwise minimum ⋮ Unboundedness problems for machines with reversal-bounded counters ⋮ Input-Position-Restricted Models of Language Acceptors ⋮ Queue Automata: Foundations and Developments ⋮ On the Density of Context-Free and Counter Languages ⋮ Recent advances on reachability problems for valence systems (invited talk) ⋮ Unnamed Item ⋮ ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS ⋮ Bad News on Decision Problems for Patterns ⋮ ON STATELESS AUTOMATA AND P SYSTEMS ⋮ Inclusion is undecidable for pattern languages ⋮ New decidability results concerning two-way counter machines and applications ⋮ Reachability in Parameterized Systems: All Flavors of Threshold Automata ⋮ Multi-Sequential Word Relations ⋮ HOW TO SYNCHRONIZE THE HEADS OF A MULTITAPE AUTOMATON ⋮ Reversal-bounded multicounter ?-machines ⋮ VERIFICATION IN QUEUE-CONNECTED MULTICOUNTER MACHINES ⋮ THE EXISTENCE OF ω-CHAINS FOR TRANSITIVE MIXED LINEAR RELATIONS AND ITS APPLICATIONS ⋮ On Stateless Multicounter Machines ⋮ On the Boundedness Property of Semilinear Sets ⋮ State grammars with stores ⋮ CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES ⋮ On the Ambiguity and Finite-Valuedness Problems in Acceptors and Transducers ⋮ Reachability in Timed Counter Systems ⋮ Restricted one-counter machines with undecidable universe problems ⋮ Decidable models of integer-manipulating programs with recursive parallelism ⋮ Unnamed Item ⋮ Variations of checking stack automata: obtaining unexpected decidability properties ⋮ SUBLINEARLY SPACE BOUNDED ITERATIVE ARRAYS ⋮ On the Containment and Equivalence Problems for GSMs, Transducers, and Linear CFGs ⋮ On Synchronized Multitape and Multihead Automata ⋮ Returning Parallel Communicating Finite Automata with Communication Bounds: Hierarchies, Decidabilities, and Undecidabilities ⋮ New Results on Vector and Homing Vector Automata ⋮ Iterating Octagons ⋮ Input-driven multi-counter automata ⋮ Two-Party Watson-Crick Computations ⋮ A Polynomial Time Match Test for Large Classes of Extended Regular Expressions ⋮ One-Reversal Counter Machines and Multihead Automata: Revisited ⋮ ON STRONG REVERSIBILITY IN P SYSTEMS AND RELATED PROBLEMS ⋮ FORMAL MODELLING OF VIRAL GENE COMPRESSION ⋮ On Families of Full Trios Containing Counter Machine Languages ⋮ Unnamed Item ⋮ Cellular Automata with Sparse Communication ⋮ PATH DECOMPOSITION AND SEMILINEARITY OF PETRI NETS ⋮ Descriptional Complexity of Bounded Regular Languages ⋮ Decision Problems for Finite Automata over Infinite Algebraic Structures ⋮ On Bounded Semilinear Languages, Counter Machines, and Finite-Index ET0L ⋮ Unnamed Item ⋮ Linear-time temporal logics with Presburger constraints: an overview ★ ⋮ On the Teaching Complexity of Linear Sets ⋮ Characterizations of the decidability of some problems for regular trace languages ⋮ UNAMBIGUOUS CONSTRAINED AUTOMATA ⋮ BOUNDED PARIKH AUTOMATA ⋮ SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS ⋮ ON REACHABILITY AND SAFETY IN INFINITE-STATE SYSTEMS ⋮ Unnamed Item ⋮ Semilinearity of Families of Languages ⋮ Two-way counter machines and finite-state transducers† ⋮ On Computational Power of Partially Blind Automata ⋮ On the Decidability of the Equivalence Problem for Monadic Recursive Programs ⋮ The effect of end-markers on counter machines and commutativity ⋮ Some decision problems concerning semilinearity and commutation. ⋮ Presburger liveness verification of discrete timed automata. ⋮ Eliminating the storage tape in reachability constructions. ⋮ On computational complexity of graph inference from counting ⋮ On two-way FA with monotonic counters and quadratic Diophantine equations ⋮ Catalytic P systems, semilinear sets, and vector addition systems ⋮ Transducers and the decidability of independence in free monoids ⋮ An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines ⋮ Reversal-bounded nondeterministic multicounter machines and complementation ⋮ Simulating one-reversal multicounter machines by partially blind multihead finite automata ⋮ Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable ⋮ Representations of language families by homomorphic equality operations and generalized equality sets ⋮ On the decidability of some problems about rational subsets of free partially commutative monoids ⋮ On reversal bounded alternating Turing machines ⋮ Quantifying communication in synchronized languages ⋮ Ordered multi-stack visibly pushdown automata ⋮ Pushdown automata with reversal-bounded counters ⋮ On the complexity of decision problems for counter machines with applications to coding theory ⋮ On selective unboundedness of VASS ⋮ On the freeze quantifier in Constraint LTL: Decidability and complexity ⋮ On the conjecture \(\mathcal {L}_{\mathsf {DFCM}}\subsetneq \mathsf {RCM}\)

This page was built for publication: Reversal-Bounded Multicounter Machines and Their Decision Problems