A linear-time simulation of deterministic d-limited automata

DOI10.1007/978-3-030-81508-0_28MaRDI QIDQ832958zbMATH OpenOpenAlexFDO

Authors Alexander A. Rubtsov

Publication date 25 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-81508-0_28

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• scientific article; zbMATH DE number 3936519 (Why is no real title available?)
• scientific article; zbMATH DE number 5593330 (Why is no real title available?)
• scientific article; zbMATH DE number 3254906 (Why is no real title available?)
• A Second Course in Formal Languages and Automata Theory
• A generalization of context-free determinism
• Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!
• Concatenation of inputs in a two-way automaton
• Fast context-free grammar parsing requires fast Boolean matrix multiplication
• General context-free recognition in less than cubic time
• If the current clique algorithms are optimal, so is Valiant's parser
• Limited automata and context-free languages
• Limited automata: properties, complexity and variants
• Linear-time limited automata
• On the translation of languages from left to right
• One-tape, off-line Turing machine computations
• Parsing algorithms with backtrack
• Parsing expression grammars: a recognition-based syntactic foundation
• Regular Closure of Deterministic Languages
• Simulation of two-way pushdown automata revisited
• Theory of one-tape linear-time Turing machines

Cited in

(1)

• scientific article; zbMATH DE number 1927559 (Why is no real title available?)

This page was built for publication: A linear-time simulation of deterministic \(d\)-limited automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q832958)