Characterization and complexity results on jumping finite automata
From MaRDI portal
Publication:2357104
DOI10.1016/j.tcs.2016.07.006zbMath1371.68148arXiv1512.00482OpenAlexW2963905619WikidataQ59864883 ScholiaQ59864883MaRDI QIDQ2357104
Markus L. Schmid, Meenakshi Paramasivan, Henning Fernau, Vojtěch Vorel
Publication date: 19 June 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1512.00482
NP-hard problemssemilinear setscommutative languagesexponential-time hypothesisshuffle expressionsjumping finite automata
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Automata-theoretical regularity characterizations for the iterated shuffle on commutative regular languages ⋮ Problems on finite automata and the exponential time hypothesis ⋮ A jumping \(5'\rightarrow 3'\) Watson-Crick finite automata model ⋮ Regularity Conditions for Iterated Shuffle on Commutative Regular Languages ⋮ Jumping automata over Infinite words ⋮ The effect of jumping modes on various automata models ⋮ Unnamed Item ⋮ Operational State Complexity and Decidability of Jumping Finite Automata ⋮ Constrained synchronization and commutativity ⋮ On Basic Properties of Jumping Finite Automata ⋮ Properties of right one-way jumping finite automata ⋮ Enhancement of automata with jumping modes ⋮ On double-jumping finite automata and their closure properties ⋮ Regular and linear permutation languages ⋮ Two Results on Discontinuous Input Processing ⋮ Problems on Finite Automata and the Exponential Time Hypothesis ⋮ 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 ⋮ Regularity conditions for iterated shuffle on commutative regular languages ⋮ The commutative closure of shuffle languages over group languages is regular
Cites Work
- Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
- The expressive power of the shuffle product
- First-order logics: some characterizations and closure properties
- On regularity of context-free languages
- Commutative one-counter languages are regular
- Infinite hierarchy of shuffle expressions over a finite alphabet
- Extending regular expressions with iterated shuffle
- On commutative context-free languages
- Algorithms for determining relative star height and star height
- Shuffle on trajectories: Syntactic constraints
- Cônes rationnels commutatifs
- Flow languages equal recursively enumerable languages
- Relations of flow languages to Petri net languages
- The power of synchronizing operations on strings
- The universe problem for unrestricted flow languages
- Remarks on blind and partially blind one-way multicounter machines
- Remarks about commutative context-free languages
- Scattered deletion and commutativity
- On distributed catenation
- Shuffle languages are in P
- Which problems have strongly exponential complexity?
- Sequential grammars and automata with valences
- The emptiness problem for valence automata or: another decidable extension of Petri nets
- Aspects of shuffle and deletion on trajectories
- Parikh's theorem: a simple and direct automaton construction
- Recent advances in formal languages and applications.
- Semigroups, Presburger formulas, and languages
- Transition graphs and the star-height of regular events
- Rational sets in commutative monoids
- AFL with the semilinear property
- General properties of star height of regular events
- Star height of certain families of regular events
- The Shuffle Product: New Research Directions
- Minimization and Characterizations for Biautomata
- Two Results on Discontinuous Input Processing
- Problems on Finite Automata and the Exponential Time Hypothesis
- BOUNDED PARIKH AUTOMATA
- Jumping Finite Automata: Characterizations and Complexity
- On a Hierarchy of Languages with Catenation and Shuffle
- Commutative grammars: The complexity of uniform word problems
- Regular languages of star height one
- Jumping Grammars
- Learning Commutative Regular Languages
- An Algorithm for the General Petri Net Reachability Problem
- Software Descriptions with Flow Expressions
- On biautomata
- ON A HIERARCHY OF PERMUTATION LANGUAGES
- CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
- JUMPING FINITE AUTOMATA
- Complexity of Problems of Commutative Grammars
- On the Exact Block Cover Problem
- Bounded Algol-Like Languages
- On Context-Free Languages
- A note on undecidable properties of formal languages
- Extended finite automata over groups
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Characterization and complexity results on jumping finite automata
