Deterministic one-counter automata
From MaRDI portal
Publication:1218272
DOI10.1016/S0022-0000(75)80005-5zbMath0307.68038OpenAlexW2115082275MaRDI QIDQ1218272
Michael S. Paterson, Leslie G. Valiant
Publication date: 1975
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(75)80005-5
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)
Related Items (52)
Countdown games, and simulation on (succinct) one-counter nets ⋮ The equivalence and inclusion problems for NTS languages ⋮ A fast algorithm to decide on the equivalence of stateless DPDA ⋮ Trace Inclusion for One-Counter Nets Revisited ⋮ The complexity of finding SUBSEQ\((A)\) ⋮ Trace inclusion for one-counter nets revisited ⋮ Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ Bisimulation equivalence and regularity for real-time one-counter automata ⋮ On the conjecture \(\mathcal {L}_{\mathsf {DFCM}}\subsetneq \mathsf {RCM}\) ⋮ On some decision questions concerning pushdown machines ⋮ Unnamed Item ⋮ Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages ⋮ The equivalence problem for deterministic pushdown automata is decidable ⋮ Effective bounds for certain functions concerning prime numbers ⋮ Decision problems for pushdown threads ⋮ Superdeterministic DPDAs: The method of accepting does affect decision problems ⋮ Efficient learning of real time one-counter automata ⋮ Coverability in 2-VASS with one unary counter is in NP ⋮ The different shades of infinite session types ⋮ Unnamed Item ⋮ The complexity of decision problems for finite-turn multicounter machines ⋮ The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine ⋮ On the decidability of equivalence for deterministic pushdown transducers ⋮ DPDA's in 'Atomic normal form' and applications to equivalence problems ⋮ New techniques for proving the decidability of equivalence problem ⋮ Unnamed Item ⋮ New decidability results concerning two-way counter machines and applications ⋮ Equivalence of deterministic pushdown automata revisited ⋮ Simple context-free languages and free monadic recursion schemes ⋮ A result on the equivalence problem for deterministic pushdown automata ⋮ Restricted one-counter machines with undecidable universe problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On equivalence and subclass containment problems for deterministic context-free languages ⋮ Two decidability results for deterministic pushdown automata ⋮ Some decision problems concerning sequential transducers and checking automata ⋮ On equivalence of grammars through transformation trees ⋮ A technique for proving decidability of containment and equivalence of linear constraint queries ⋮ Risk assessment for one-counter threads ⋮ On the inference of strategies ⋮ Decidability of the equivalence problem for deterministic pushdown automata ⋮ Boundedness, empty channel detection, and synchronization for communicating finite automata ⋮ Synchronizable deterministic pushdown automata and the decidability of their equivalence ⋮ The Complexity of Flat Freeze LTL ⋮ A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems ⋮ Inference of deterministic one-counter languages ⋮ Counter machines and verification problems. ⋮ Decidability of bisimilarity for one-counter processes. ⋮ An extended direct branching algorithm for checking equivalence of deterministic pushdown automata ⋮ On the Decidability of the Equivalence Problem for Monadic Recursive Programs ⋮ Majoration explicite de l'ordre maximum d'un élément du groupe symétrique
Cites Work
This page was built for publication: Deterministic one-counter automata
