TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
type: Item
instance of: scholarly article
title: TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
zbMATH Open document ID: 1156.68021
DOI: 10.1142/S012905410800598X
author: Carlo Mereghetti
published in: International Journal of Foundations of Computer Science
publication date: 2008-09-25T00:00:00Z
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 5346925
zbMATH Keywords: computational lower bounds
zbMATH Keywords: regular languages
MaRDI profile type: MaRDI publication profile
cites work: An optimal lower bound for nonregular languages
cites work: The alternation hierarchy for sublogarithmic space is infinite
cites work: Alternation
cites work: Space bounds for processing contentless inputs
cites work: Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
cites work: Bridging across the \(\log(n)\) space frontier
cites work: Sublogarithmic Bounds on Space and Reversals
cites work: Converting two-way nondeterministic unary automata into simpler automata.
cites work: Complementing two-way finite automata
cites work: One-tape, off-line Turing machine computations
cites work: A tradeoff theorem for space and reversal
cites work: Some Results on Tape-Bounded Turing Machines
cites work: Deterministic versus nondeterministic space in terms of synchronized alternating machines
cites work: ${\text{ASPACE}}(o(\log \log n))$ is Regular
cites work: The Sublogarithmic Alternating Space World
cites work: A remark on middle space bounded alternating Turing machines
cites work: Optimal simulations between unary automata
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: ON THE POWER OF ONE-WAY GLOBALLY DETERMINISTIC SYNCHRONIZED ALTERNATING TURING MACHINES AND MULTIHEAD AUTOMATA
cites work: Remarks on languages acceptable in log log n space
Recommended article: Strong optimal lower bounds for Turing machines that accept nonregular languages
Recommended article: An optimal lower bound for nonregular languages
Recommended article: Q3692869
Recommended article: TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
Recommended article: Q3747727
description: scientific article; zbMATH DE number 5346925