Unboundedness problems for machines with reversal-bounded counters

DOI10.1007/978-3-031-30829-1_12arXiv2301.10198OpenAlexW4366547923MaRDI QIDQ6091196

Oscar H. Ibarra, Pascal Baumann, Flavio D'Alessandro, Ian McQuillan, Lia Schütze, Georg Zetzsche, Moses Ganardi

Publication date: 24 November 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2301.10198

zbMATH Keywords

complexityboundednessdecidabilityunboundednessformal languagescounter automatapushdownReversal-bounded

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The algebraic theory of Parikh automata
• Pushdown automata with reversal-bounded counters
• The complexity of decision problems for finite-turn multicounter machines
• A structure to decide reachability in Petri nets
• Reversal-bounded multipushdown machines
• On derivation trees of indexed grammars - an extension of the uvwxy- theorem
• Remarks on blind and partially blind one-way multicounter machines
• An example of an indexed language of intermediate growth
• Refining the hierarchy of blind multicounter languages and twist-closed trios.
• Sequential grammars and automata with valences
• Counter machines and verification problems.
• Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity
• On the commutative equivalence of bounded context-free and regular languages: the semi-linear case
• Languages ordered by the subword order
• Inclusion between the frontier language of a non-deterministic recursive program scheme and the Dyck language is undecidable
• Unboundedness and downward closures of higher-order pushdown automata
• BOUNDED PARIKH AUTOMATA
• A Perfect Model for Bounded Verification
• Integer Vector Addition Systems with States
• An Approach to Computing Downward Closures
• On the Density of Context-Free and Counter Languages
• FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME
• Reversal-Bounded Counter Machines Revisited
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• The Complexity of Downward Closure Comparisons
• Demystifying Reachability in Vector Addition Systems
• The Diagonal Problem for Higher-Order Recursion Schemes is Decidable
• On the Density of Context-Free and Counter Languages
• Affine Parikh automata
• CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
• Unboundedness Problems for Languages of Vector Addition Systems.
• Minimal solutions of linear diophantine systems : bounds and algorithms
• The Complexity of the Diagonal Problem for Recursion Schemes
• Automated Deduction – CADE-20
• Bounded Algol-Like Languages
• On Context-Free Languages
• On the equivalence and containment problems for context-free languages
• Two-Way Parikh Automata
• Cost Automata, Safe Schemes, and Downward Closures

This page was built for publication: Unboundedness problems for machines with reversal-bounded counters