New Decidability Results Concerning Two-Way Counter Machines
From MaRDI portal
Publication:4326857
DOI10.1137/S0097539792240625zbMath0828.68075MaRDI QIDQ4326857
Hui Wang, Oscar H. Ibarra, Tao Jiang, Nicholas Q. Tran
Publication date: 2 January 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Related Items
On the solvability of a class of Diophantine equations and applications, Some decision problems concerning semilinearity and commutation., On two-way FA with monotonic counters and quadratic Diophantine equations, On the complexity of decision problems for counter machines with applications to coding theory, Deletion operations on deterministic families of automata, Similarity in languages and programs, On the complexity of decision problems for some classes of machines and applications, On counting functions and slenderness of languages, Insertion operations on deterministic reversal-bounded counter machines, Generalized discrete timed automata: Decidable approximations for safety verification., Pushdown timed automata: A binary reachability characterization and safety verification., On synchronized multi-tape and multi-head automata, Descriptional complexity of two-way pushdown automata with restricted head reversals, ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS, Accepting runs in a two-way finite automaton, On two-way nondeterministic finite automata with one reversal-bounded counter, Variations of checking stack automata: obtaining unexpected decidability properties, On store languages of language acceptors, On Synchronized Multitape and Multihead Automata, Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals, A technique for proving decidability of containment and equivalence of linear constraint queries, On decidability and closure properties of language classes with respect to bio-operations, Unnamed Item, On composition and lookahead delegation of \(e\)-services modeled by automata, SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS, Counter machines and verification problems.
