TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE

DOI10.1142/S012905410800598XzbMath1156.68021MaRDI QIDQ3526538

Carlo Mereghetti

Publication date: 25 September 2008

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

regular languagescomputational lower bounds

Mathematics Subject Classification ID

Related Items (11)

Iterated uniform finite-state transducers on unary languages ⋮ Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers* ⋮ Unnamed Item ⋮ Iterated uniform finite-state transducers on unary languages ⋮ Minimal Size of Counters for (Real-Time) Multicounter Automata ⋮ Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ SUBLINEARLY SPACE BOUNDED ITERATIVE ARRAYS ⋮ 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

Cites Work

• A tradeoff theorem for space and reversal
• Remarks on languages acceptable in log log n space
• Space bounds for processing contentless inputs
• Bridging across the \(\log(n)\) space frontier
• The alternation hierarchy for sublogarithmic space is infinite
• An optimal lower bound for nonregular languages
• Deterministic versus nondeterministic space in terms of synchronized alternating machines
• A remark on middle space bounded alternating Turing machines
• Converting two-way nondeterministic unary automata into simpler automata.
• Relationships between nondeterministic and deterministic tape complexities
• Complementing two-way finite automata
• Optimal Simulations between Unary Automata
• Alternation
• Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
• ${\text{ASPACE}}(o(\log \log n))$ is Regular
• Sublogarithmic Bounds on Space and Reversals
• ON THE POWER OF ONE-WAY GLOBALLY DETERMINISTIC SYNCHRONIZED ALTERNATING TURING MACHINES AND MULTIHEAD AUTOMATA
• The Sublogarithmic Alternating Space World
• Some Results on Tape-Bounded Turing Machines
• One-tape, off-line Turing machine computations

This page was built for publication: TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE