Two-way unary automata versus logarithmic space
type: Item
instance of: scholarly article
title: Two-way unary automata versus logarithmic space
zbMATH Open document ID: 1216.68143
author: Viliam Geffert
author: Giovanni Pighizzini
published in: Information and Computation
publication date: 2011-07-18T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5925498
zbMATH Keywords: unary regular languages
zbMATH Keywords: finite automata
zbMATH Keywords: state complexity
zbMATH Keywords: logarithmic space
zbMATH Keywords: space complexity
MaRDI profile type: Publication
full work available at URL: j.ic.2011.03.003
OpenAlex ID: W2005397173
Wikidata QID: Q61677514
cites work: Q4139689
cites work: State-complexity of finite-state devices, state compressibility and incompressibility
cites work: Converting two-way nondeterministic unary automata into simpler automata.
cites work: Q3862379
cites work: Q4449194
cites work: Space-bounded reducibility among combinatorial problems
cites work: Q3517105
cites work: Size Complexity of Two-Way Finite Automata
cites work: Turing machines that take advice
cites work: DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
cites work: Q4503152
cites work: Two-way deterministic finite automata are exponentially more succinct than sweeping automata
cites work: Q5541339
cites work: Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
cites work: Making Nondeterminism Unambiguous
cites work: Nondeterminism and the size of two way finite automata
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Q5541340
cites work: Lower bounds on the size of sweeping automata
cites work: Turing machines with sublogarithmic space
cites work: Unary finite automata vs. arithmetic progressions
DOI: 10.1016/J.IC.2011.03.003
Recommended article: Two-Way Unary Automata versus Logarithmic Space
Recommended article: Two-way automata versus logarithmic space
Recommended article: Two-Way Automata versus Logarithmic Space
Recommended article: Q4503152
Recommended article: Two-Way Non-Uniform Finite Automata
Recommended article: Two-way non-uniform finite automata
Recommended article: Q4785462
Recommended article: State complexity of operations on two-way finite automata over a unary alphabet
Recommended article: Unary Languages Recognized by Two-Way One-Counter Automata
Recommended article: On the transformation of two-way deterministic finite automata to unambiguous finite automata
description: scientific article; zbMATH DE number 5925498