A linear-time simulation of deterministic \(d\)-limited automata
From MaRDI portal
Publication:832958
DOI10.1007/978-3-030-81508-0_28OpenAlexW3188431180MaRDI QIDQ832958
Publication date: 25 March 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-81508-0_28
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Theory of one-tape linear-time Turing machines
- Concatenation of inputs in a two-way automaton
- General context-free recognition in less than cubic time
- Limited automata: properties, complexity and variants
- Limited Automata and Context-Free Languages
- Fast context-free grammar parsing requires fast boolean matrix multiplication
- Parsing expression grammars
- A Second Course in Formal Languages and Automata Theory
- Parsing algorithms with backtrack
- Regular Closure of Deterministic Languages
- If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
- Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!
- A generalization of context-free determinism
- One-tape, off-line Turing machine computations
- On the translation of languages from left to right
- The computational power of parsing expression grammars
- Linear-time limited automata