On two-way weak counter machines

DOI10.1007/BF01692057zbMath0629.68055MaRDI QIDQ3766856

Tat-Hung Chan

Publication date: 1987

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

Turing machinestwo-way finite automatadeterministic machinesnondeterministic machinestwo-way counter machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

New decidability results concerning two-way counter machines and applications ⋮ A unified approach for deciding the existence of certain petri net paths

Cites Work

• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Remarks on two-way automata with weak-counters
• The complexity of decision problems for finite-turn multicounter machines
• Two-way deterministic multi-weak-counter machines
• Reversal-bounded multipushdown machines
• Remarks on the complexity of nondeterministic counter languages
• Relating refined space complexity classes
• The covering and boundedness problems for vector addition systems
• Remarks on blind and partially blind one-way multicounter machines
• Parallel program schemata
• On non-determinacy in simple computing devices
• Restricted one-counter machines with undecidable universe problems
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Counter machines and counter languages