Two-way automata and length-preserving homomorphisms
From MaRDI portal
Publication:4879206
DOI10.1007/BF01201276zbMath0846.68071MaRDI QIDQ4879206
Publication date: 27 May 1996
Published in: Mathematical Systems Theory (Search for Journal in Brave)
68Q45: Formal languages and automata
Related Items
State-complexity of finite-state devices, state compressibility and incompressibility, A note on the space complexity of some decision problems for finite automata, Formal languages defined by uniform substitutions, Complexity results for two-way and multi-pebble automata and their logics, Counting with Probabilistic and Ultrametric Finite Automata, Size Complexity of Two-Way Finite Automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On equations for regular languages, finite automata, and sequential networks
- Partial orders on words, minimal elements of regular languages, and state complexity
- Succinct representation of regular languages by Boolean automata. II
- Finite automata and unary languages
- Concatenation of inputs in a two-way automaton
- Halting space-bounded computations
- Tree-size bounded alternation
- Succinct representation of regular languages by Boolean automata
- On uniform circuit complexity
- Alternation with a pebble
- A note on the space complexity of some decision problems for finite automata
- An NP-complete language accepted in linear time by a one-tape Turing machine
- Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
- Hierarchies of Turing machines with restricted tape alphabet size
- On the pre-AFL of \([lg\;n\) space and related families of languages]
- Alternating Pushdown and Stack Automata
- A taxonomy of problems with fast parallel algorithms
- Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
- Finite monoids and the fine structure of NC 1
- Alternation
- Bounds to Complexities of Networks for Sorting and for Switching
- State-complexity of finite-state devices, state compressibility and incompressibility
- Nondeterminism and the size of two way finite automata
- Quasi-realtime languages
- One-tape, off-line Turing machine computations
