1-limited automata: witness languages and techniques

MaRDI QIDQ5867525zbMATH OpenFDO

Authors Giovanni Pighizzini, Luca Prigioniero, Šimon Sádovský

Publication date 14 September 2022

Full work available at URL http://www.jalc.de/issues/2022/issue_27_1-3/jalc-2022-229-244.php

zbMATH Keywords

descriptional complexityregular languageslimited automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Limited automata and regular languages
• Limited automata and regular languages
• Limited automata and unary languages
• Limited automata and unary languages
• Limited automata: properties, complexity and variants

Cites work

• scientific article; zbMATH DE number 3936518 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 1502111 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• scientific article; zbMATH DE number 3254906 (Why is no real title available?)
• A generalization of context-free determinism
• Behavioral strengths and weaknesses of various models of limited automata
• Descriptional complexity of limited automata
• Limited automata and context-free languages
• Limited automata and regular languages
• Limited automata and unary languages
• Limited automata: properties, complexity and variants
• Linear-time limited automata
• Nondeterminism and the size of two way finite automata
• Reversible limited automata

Cited in

(4)

• One-way permutations and self-witnessing languages
• Performing regular operations with 1-limited automata
• Performing regular operations with 1-limited automata
• Once-Marking and Always-Marking 1-Limited Automata

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: 1-limited automata: witness languages and techniques

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