Two-way automata and length-preserving homomorphisms
From MaRDI portal
Publication:4879206
Recommendations
Cites work
- A note on the space complexity of some decision problems for finite automata
- A taxonomy of problems with fast parallel algorithms
- Alternating Pushdown and Stack Automata
- Alternation
- Alternation with a pebble
- An NP-complete language accepted in linear time by a one-tape Turing machine
- Bounds to Complexities of Networks for Sorting and for Switching
- Concatenation of inputs in a two-way automaton
- Finite automata and unary languages
- Finite monoids and the fine structure of NC 1
- Halting space-bounded computations
- Hierarchies of Turing machines with restricted tape alphabet size
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3774850 (Why is no real title available?)
- scientific article; zbMATH DE number 47903 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3523640 (Why is no real title available?)
- scientific article; zbMATH DE number 3607492 (Why is no real title available?)
- scientific article; zbMATH DE number 3428547 (Why is no real title available?)
- scientific article; zbMATH DE number 3254906 (Why is no real title available?)
- Nondeterminism and the size of two way finite automata
- On equations for regular languages, finite automata, and sequential networks
- On the pre-AFL of \([lg\;n]\) space and related families of languages
- On uniform circuit complexity
- One-tape, off-line Turing machine computations
- Partial orders on words, minimal elements of regular languages, and state complexity
- Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
- Quasi-realtime languages
- State-complexity of finite-state devices, state compressibility and incompressibility
- Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
- Succinct representation of regular languages by Boolean automata
- Succinct representation of regular languages by Boolean automata. II
- Tree-size bounded alternation
Cited in
(15)- A note on the reduction of two-way automata to one-way automata
- 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
- Alternation in two-way finite automata
- Two-way automata versus logarithmic space
- Normality and two-way automata
- Two-Way Automata Characterizations of L/poly versus NL
- Counting with probabilistic and ultrametric finite automata
- Two-Way Automata versus Logarithmic Space
- Size Complexity of Two-Way Finite Automata
- Complexity results for multi-pebble automata and their logics
- Translation from classical two-way automata to pebble two-way automata
- State-complexity of finite-state devices, state compressibility and incompressibility
- On the translation of automata to linear temporal logic
This page was built for publication: Two-way automata and length-preserving homomorphisms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4879206)
