LIMITED AUTOMATA AND REGULAR LANGUAGES

DOI10.1142/S0129054114400140zbMath1320.68114WikidataQ61677490 ScholiaQ61677490MaRDI QIDQ5173292

Giovanni Pighizzini, Andrea Pisoni

Publication date: 9 February 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

Turing machinesfinite automataformal languagescontext-free languagesregular languagesdescriptional complexity

Mathematics Subject Classification ID

Related Items (16)

Deterministic Stack Transducers ⋮ Performing regular operations with 1-limited automata ⋮ Reversible Limited Automata ⋮ Unnamed Item ⋮ Nondeterministic auxiliary depth-bounded storage automata and semi-unbounded fan-in cascading circuits (extended abstract) ⋮ Two-way machines and de Bruijn words ⋮ Once-Marking and Always-Marking 1-Limited Automata ⋮ Between SC and LOGDCFL: families of languages accepted by polynomial-time logarithmic-space deterministic auxiliary depth-\(k\) storage automata ⋮ Descriptional complexity of limited automata ⋮ Linear-time limited automata ⋮ Limited automata and unary languages ⋮ Deterministic Stack Transducers ⋮ Descriptional complexity of regular languages ⋮ On Simulation Cost of Unary Limited Automata ⋮ Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata ⋮ Converting nondeterministic two-way automata into small deterministic linear-time machines

Cites Work

• Descriptional and computational complexity of finite automata -- a survey
• Finite automata and unary languages
• Intersection and union of regular languages and state complexity
• Optimal Simulations between Unary Automata
• Non-erasing Variants of the Chomsky–Schützenberger Theorem
• DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
• State-complexity of finite-state devices, state compressibility and incompressibility
• A generalization of context-free determinism
• One-tape, off-line Turing machine computations
• Unnamed Item

This page was built for publication: LIMITED AUTOMATA AND REGULAR LANGUAGES