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

• Characterization and complexity results on jumping finite automata
• 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?)
• 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

(28)

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

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)