On basic properties of jumping finite automata

DOI10.1142/S0129054118500016MaRDI QIDQ4639928zbMATH OpenFDO

Authors Vojtěch Vorel

Publication date 14 May 2018

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

Full work available at URL https://arxiv.org/abs/1511.08396

zbMATH Keywords

insertion-deletion systemsjumping finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We complete the initial study of jumping finite automata, which was started in a former article of Meduna and Zemek citep{athMED1}. The open questions about basic closure properties are solved. Besides this, we correct erroneous results presented in the article. Finally, we point out important relations between jumping finite automata and some other models studied in the literature.

Recommendations

• Characterization and complexity results on jumping finite automata
• On double-jumping finite automata and their closure properties
• Operational state complexity and decidability of jumping finite automata
• Operational state complexity and decidability of jumping finite automata
• One-way jumping finite automata

Cites work

• scientific article; zbMATH DE number 4160148 (Why is no real title available?)
• scientific article; zbMATH DE number 3902039 (Why is no real title available?)
• scientific article; zbMATH DE number 1236223 (Why is no real title available?)
• Characterization and complexity results on jumping finite automata
• Insertion and deletion closure of languages
• Insertion languages
• Jumping finite automata
• On regularity of context-free languages
• Recent developments on insertion-deletion systems
• Regulated grammars and automata
• Small size insertion and deletion systems
• Two results on discontinuous input processing

Cited in

(26)

• Two-dimensional jumping finite automata
• Jumping finite automata: characterizations and complexity
• One-way jumping finite automata
• Nondeterministic right one-way jumping finite automata
• Operational state complexity and decidability of jumping finite automata
• The effect of jumping modes on various automata models
• Two results on discontinuous input processing
• New results on semilinear sets and variants of jumping finite automata
• Jumping automata over Infinite words
• Operational state complexity and decidability of jumping finite automata
• Two results on discontinuous input processing
• Jumping finite automata
• Decidability of right one-way jumping finite automata
• Quantitative semantics for jumping automata
• Enhancement of automata with jumping modes
• Watson-Crick jumping finite automata
• A jumping \(5'\rightarrow 3'\) Watson-Crick finite automata model
• Characterization and complexity results on jumping finite automata
• scientific article; zbMATH DE number 1741789 (Why is no real title available?)
• Nondeterministic right one-way jumping finite automata (extended abstract)
• Jumping Automata for Uniform Strategies
• Jumping automata over infinite words
• Properties of right one-way jumping finite automata
• Properties of right one-way jumping finite automata
• On double-jumping finite automata and their closure properties
• Jumping automata must pay

This page was built for publication: On basic properties of jumping finite automata

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