Linear-time limited automata

DOI10.1016/j.tcs.2019.03.037zbMath1435.68162OpenAlexW2838627201WikidataQ128103051 ScholiaQ128103051MaRDI QIDQ5919709

Luca Prigioniero, Bruno Guillon

Publication date: 7 November 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.03.037

zbMATH Keywords

regular languagesdescriptional complexitylimited automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Classical models of computation (Turing machines, etc.) (68Q04)

Related Items

A linear-time simulation of deterministic \(d\)-limited automata ⋮ Performing regular operations with 1-limited automata ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Theory of one-tape linear-time Turing machines
• Halting space-bounded computations
• Descriptional complexity of limited automata
• Complementing two-way finite automata
• Limited Automata and Context-Free Languages
• LIMITED AUTOMATA AND REGULAR LANGUAGES
• Predicate Characterizations in the Polynomial-Size Hierarchy
• Weight-Reducing Hennie Machines and Their Descriptional Complexity
• A generalization of context-free determinism
• One-tape, off-line Turing machine computations
• Linear-time limited automata
• Limited automata and unary languages

This page was built for publication: Linear-time limited automata