TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
From MaRDI portal
(Redirected from Publication:3526538)
Recommendations
- Strong optimal lower bounds for Turing machines that accept nonregular languages
- An optimal lower bound for nonregular languages
- scientific article; zbMATH DE number 3917711
- TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
- scientific article; zbMATH DE number 3984575
Cites work
- ${\text{ASPACE}}(o(\log \log n))$ is Regular
- A remark on middle space bounded alternating Turing machines
- A tradeoff theorem for space and reversal
- Alternation
- An optimal lower bound for nonregular languages
- Bridging across the (n) space frontier
- Complementing two-way finite automata
- Converting two-way nondeterministic unary automata into simpler automata.
- Deterministic versus nondeterministic space in terms of synchronized alternating machines
- ON THE POWER OF ONE-WAY GLOBALLY DETERMINISTIC SYNCHRONIZED ALTERNATING TURING MACHINES AND MULTIHEAD AUTOMATA
- One-tape, off-line Turing machine computations
- Optimal simulations between unary automata
- Relationships between nondeterministic and deterministic tape complexities
- Remarks on languages acceptable in log log n space
- Some Results on Tape-Bounded Turing Machines
- Space bounds for processing contentless inputs
- Sublogarithmic Bounds on Space and Reversals
- Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
- The alternation hierarchy for sublogarithmic space is infinite
- The Sublogarithmic Alternating Space World
Cited in
(14)- The descriptional power of queue automata of constant length
- New results on the minimum amount of useful space
- Alternating demon space is closed under complement and other simulations for sublogarithmic space
- Sublinearly space bounded iterative arrays
- Strong optimal lower bounds for Turing machines that accept nonregular languages
- Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*
- Alternating space is closed under complement and other simulations for sublogarithmic space
- Minimal Size of Counters for (Real-Time) Multicounter Automata
- Investigations on automata and languages over a unary alphabet
- scientific article; zbMATH DE number 7770052 (Why is no real title available?)
- Iterated uniform finite-state transducers on unary languages
- Push complexity: optimal bounds and unary inputs
- Push complexity: optimal bounds and decidability
- Iterated uniform finite-state transducers on unary languages
This page was built for publication: TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3526538)
