Remarks on the complexity of nondeterministic counter languages
From MaRDI portal
Cites work
- A generator of context-sensitive languages
- A note on AFLs and bounded erasing
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Comparing complexity classes
- Counter machines and counter languages
- Erasable context-free languages
- scientific article; zbMATH DE number 3131080 (Why is no real title available?)
- On Languages Accepted in Polynomial Time
- On two-way multihead automata
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- Relationships between nondeterministic and deterministic tape complexities
- Some Results on Tape-Bounded Turing Machines
- Tape-bounded Turing acceptors and principal AFLs
- Time and tape complexity of pushdown automaton languages
- Translational lemmas, polynomial time, and \((\log n)^j\)-space
Cited in
(31)- Alternating multicounter machines with constant number of reversals
- On-line n-bounded multicounter automata
- Three-way two-dimensional multicounter automata
- The complexity of decision problems for finite-turn multicounter machines
- Two-way deterministic multi-weak-counter machines
- A note on realtime one-way synchronized alternating one-counter automata
- Remarks on blind and partially blind one-way multicounter machines
- One-way simple multihead finite automata
- Refining the hierarchy of blind multicounter languages and twist-closed trios.
- Computations on register machines with counters
- On some bounded semiAFLs and AFLs
- On partially blind multihead finite automata.
- On three-way two-dimensional multicounter automata
- On computational power of partially blind automata
- Simulations by time-bounded counter machines
- ON GROUPS AND COUNTER AUTOMATA
- Simulations by Time-Bounded Counter Machines
- scientific article; zbMATH DE number 3808971 (Why is no real title available?)
- On two-way weak counter machines
- Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
- C-graph automatic groups.
- scientific article; zbMATH DE number 3560777 (Why is no real title available?)
- scientific article; zbMATH DE number 3604381 (Why is no real title available?)
- scientific article; zbMATH DE number 3628412 (Why is no real title available?)
- Counter machines, Petri nets, and consensual computation
- Probabilistic rebound Turing machines
- Groups whose word problems are accepted by abelian G-automata
- Reversible computations of one-way counter automata
- Reachability in fixed VASS: expressiveness and lower bounds
- Zur Elimination von Prozedurschachtelungen
- A note on real-time one-way alternating multicounter machines
This page was built for publication: Remarks on the complexity of nondeterministic counter languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1228202)
