Complexity of universality and related problems for partially ordered NFAs

DOI10.1016/j.ic.2017.06.004zbMath1371.68155arXiv1609.03460OpenAlexW2519230465MaRDI QIDQ2013561

Tomáš Masopust, Michaël Thomazo, Markus Krötzsch

Publication date: 8 August 2017

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1609.03460

zbMATH Keywords

equivalenceautomatauniversalitypartial ordernondeterminisminclusion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Scattered Factor-Universality of Words ⋮ Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Unnamed Item ⋮ Absent Subsequences in Words ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ Complexity of deciding detectability in discrete event systems ⋮ On verification of D-detectability for discrete event systems ⋮ State complexity of permutation and related decision problems on alphabetical pattern constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptional and computational complexity of finite automata -- a survey
• Permutation rewriting and algorithmic verification
• Languages of R-trivial monoids
• A generalization of the Schützenberger product of finite monoids
• Classification of finite monoids: the language approach
• Space-bounded reducibility among combinatorial problems
• The inclusion problem for simple languages
• The dot-depth hierarchy of star-free languages is infinite
• Sur le produit de concatenation non ambigu
• Finite semigroup varieties of the form V*D
• On Boolean combinations forming piecewise testable languages
• Languages of dot-depth 3/2
• On the computational power of pushdown automata
• Dot-depth of star-free events
• The Complexity of Answering Conjunctive and Navigational Queries over OWL 2 EL Knowledge Bases
• Querying Regular Graph Patterns
• PARTIALLY ORDERED TWO-WAY BÜCHI AUTOMATA
• On Decidability of Intermediate Levels of Concatenation Hierarchies
• Around Dot Depth Two
• Complexity of Decision Problems for XML Schemas and Chain Regular Expressions
• Computational Parallels between the Regular and Context-Free Languages
• The equivalence problem for deterministic pushdown automata is decidable
• Separating Regular Languages with Two Quantifiers Alternations
• Deciding Definability by Deterministic Regular Expressions
• Alternative Automata Characterization of Piecewise Testable Languages
• Machines, Computations, and Universality
• One-unambiguous regular languages

This page was built for publication: Complexity of universality and related problems for partially ordered NFAs