Deterministic one-counter automata

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items

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