Operational State Complexity and Decidability of Jumping Finite Automata

DOI10.1142/S012905411940001XzbMath1415.68121OpenAlexW2920575637WikidataQ128283700 ScholiaQ128283700MaRDI QIDQ5384429

Simon Beier, Martin Kutrib, Markus Holzer

Publication date: 24 June 2019

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

Full work available at URL: https://doi.org/10.1142/s012905411940001x

zbMATH Keywords

decidabilitystate complexitysemilinear setParikh imageoperation problemjumping automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

A hierarchy of jumping restarting automata ⋮ Unnamed Item

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
• Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
• The parallel complexity of finite-state automata problems
• Characterization and complexity results on jumping finite automata
• Jumping Finite Automata: Characterizations and Complexity
• The complexity of equivalence problems for commutative grammars
• JUMPING FINITE AUTOMATA
• Complexity of Problems of Commutative Grammars
• Operational State Complexity under Parikh Equivalence
• Bounded Algol-Like Languages

This page was built for publication: Operational State Complexity and Decidability of Jumping Finite Automata