Jumping Finite Automata: Characterizations and Complexity

DOI10.1007/978-3-319-22360-5_8zbMath1465.68144OpenAlexW1132487926MaRDI QIDQ2947412

Markus L. Schmid, Henning Fernau, Meenakshi Paramasivan

Publication date: 23 September 2015

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-22360-5_8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (16)

A jumping \(5'\rightarrow 3'\) Watson-Crick finite automata model ⋮ Jumping automata over Infinite words ⋮ Unnamed Item ⋮ The effect of jumping modes on various automata models ⋮ Simulation by Rounds of Letter-to-Letter Transducers ⋮ Non-returning deterministic and nondeterministic finite automata with translucent letters ⋮ Unnamed Item ⋮ Operational State Complexity and Decidability of Jumping Finite Automata ⋮ Linear automata with translucent letters and linear context-free trace languages ⋮ Properties of right one-way jumping finite automata ⋮ Enhancement of automata with jumping modes ⋮ Two Results on Discontinuous Input Processing ⋮ Membership Problem for Two-Dimensional General Row Jumping Finite Automata ⋮ Decidability of Right One-Way Jumping Finite Automata ⋮ Nondeterministic right one-way jumping finite automata ⋮ Characterization and complexity results on jumping finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• On regularity of context-free languages
• Commutative one-counter languages are regular
• Extending regular expressions with iterated shuffle
• Algorithms for determining relative star height and star height
• The power of synchronizing operations on strings
• Shuffle languages are in P
• Parikh's theorem: a simple and direct automaton construction
• Recent advances in formal languages and applications.
• Transition graphs and the star-height of regular events
• On biautomata
• JUMPING FINITE AUTOMATA
• On the Exact Block Cover Problem
• Regulated Grammars and Automata
• On Context-Free Languages

This page was built for publication: Jumping Finite Automata: Characterizations and Complexity