Jumping finite automata: characterizations and complexity

DOI10.1007/978-3-319-22360-5_8MaRDI QIDQ2947412zbMATH OpenOpenAlexFDO

Authors Henning Fernau, Meenakshi Paramasivan, Markus L. Schmid

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)

Recommendations

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

Cites work

• Algorithms for determining relative star height and star height
• Commutative languages and their composition by consensual methods
• Commutative one-counter languages are regular
• Extending regular expressions with iterated shuffle
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 3642736 (Why is no real title available?)
• Jumping finite automata
• On biautomata
• On Context-Free Languages
• On regularity of context-free languages
• On the exact block cover problem
• Parikh's theorem: a simple and direct automaton construction
• Recent advances in formal languages and applications.
• Regulated grammars and automata
• Shuffle languages are in P
• The power of synchronizing operations on strings
• Transition graphs and the star-height of regular events

Cited in

(31)

• 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 Automata for Uniform Strategies
• Linear automata with translucent letters and linear context-free trace languages
• Jumping grammars
• On double-jumping finite automata and their closure properties
• Two-dimensional jumping finite automata
• Operational state complexity and decidability of jumping finite automata
• Membership problem for two-dimensional general row jumping finite automata
• Decidability of right one-way jumping finite automata
• Complexities for jumps and sweeps
• 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
• Simulation by Rounds of Letter-to-Letter Transducers
• Non-returning deterministic and nondeterministic finite automata with translucent letters
• Jump complexity of finite automata with translucent letters
• Non-returning finite automata with translucent letters
• Jumping automata over infinite words
• Quantitative semantics for jumping automata
• Jumping automata must pay
• Repetitive finite automata with translucent letters
• Finite automata with sets of translucent words
• On languages of transduced-input finite automata with translucent letters
• A two-dimensional infinite hierarchy for finite automata with translucent words

This page was built for publication: Jumping finite automata: characterizations and complexity

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