Remarks on the complexity of nondeterministic counter languages

DOI10.1016/0304-3975(76)90072-4zbMath0332.68039OpenAlexW1968497788MaRDI QIDQ1228202

Sheila A. Greibach

Publication date: 1976

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(76)90072-4

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Unnamed Item, On three-way two-dimensional multicounter automata, Unnamed Item, On two-way weak counter machines, \(\mathcal C\)-graph automatic groups., Groups whose word problems are accepted by abelian \(G\)-automata, On-line n-bounded multicounter automata, Three-way two-dimensional multicounter automata, Unnamed Item, The complexity of decision problems for finite-turn multicounter machines, Two-way deterministic multi-weak-counter machines, Unnamed Item, Refining the hierarchy of blind multicounter languages and twist-closed trios., Unnamed Item, Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties, Computations on register machines with counters, Counter machines, Petri nets, and consensual computation, A note on realtime one-way synchronized alternating one-counter automata, On partially blind multihead finite automata., ON GROUPS AND COUNTER AUTOMATA, Probabilistic rebound Turing machines, Remarks on blind and partially blind one-way multicounter machines, One-way simple multihead finite automata, SIMULATIONS BY TIME-BOUNDED COUNTER MACHINES, Simulations by Time-Bounded Counter Machines, Zur Elimination von Prozedurschachtelungen, On some bounded semiAFLs and AFLs, On Computational Power of Partially Blind Automata, Alternating multicounter machines with constant number of reversals, A note on real-time one-way alternating multicounter machines

Cites Work

• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Translational lemmas, polynomial time, and \((\log n)^j\)-space
• Comparing complexity classes
• Relationships between nondeterministic and deterministic tape complexities
• A generator of context-sensitive languages
• Tape-bounded Turing acceptors and principal AFLs
• On two-way multihead automata
• Erasable context-free languages
• Counter machines and counter languages
• Some Results on Tape-Bounded Turing Machines
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• On Languages Accepted in Polynomial Time
• A note on AFLs and bounded erasing
• Time and tape complexity of pushdown automaton languages