On the containment problem for deterministic multicounter machine models

DOI10.1016/J.IC.2025.105383MaRDI QIDQ6884278zbMATH OpenFDO

Authors Oscar H. Ibarra, Ian McQuillan

Publication date 15 December 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105383

zbMATH Keywords

containmentdeterminismmulticounter machinesPetri netsvector addition systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites work

• A note on semilinear sets and bounded-reversal multihead pushdown automata
• AFL with the semilinear property
• An Algorithm for the General Petri Net Reachability Problem
• Bounded Algol-Like Languages
• CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
• Deterministic context free languages
• Deterministic counter machines and parallel matching computations
• scientific article; zbMATH DE number 4035163 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• Insertion operations on deterministic reversal-bounded counter machines
• Language inclusion for boundedly-ambiguous vector addition systems is decidable
• New Decidability Results Concerning Two-Way Counter Machines
• On Context-Free Languages
• On store languages and applications
• On the containment and equivalence problems for two-way transducers
• On the reachability problem for 5-dimensional vector addition systems
• Presburger vector addition systems
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity
• Remarks on blind and partially blind one-way multicounter machines
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Reversal-bounded multipushdown machines
• Semigroups, Presburger formulas, and languages
• Semilinearity and Context-Freeness of Languages Accepted by Valence Automata
• The containment problem for unambiguous register automata and unambiguous timed automata
• The covering and boundedness problems for vector addition systems
• The effect of end-markers on counter machines and commutativity
• Unboundedness problems for machines with reversal-bounded counters

This page was built for publication: On the containment problem for deterministic multicounter machine models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6884278)