Complexity of universality and related problems for partially ordered NFAs

DOI10.1016/J.IC.2017.06.004zbMATH Open1371.68155arXiv1609.03460OpenAlexW2519230465MaRDI QIDQ2013561FDOQ2013561

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

Publication date: 8 August 2017

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

Abstract: Partially ordered nondeterminsitic finite automata (poNFAs) are NFAs whose transition relation induces a partial order on states, that is, for which cycles occur only in the form of self-loops on a single state. A poNFA is universal if it accepts all words over its input alphabet. Deciding universality is PSPACE-complete for poNFAs, and we show that this remains true even when restricting to a fixed alphabet. This is nontrivial since standard encodings of alphabet symbols in, e.g., binary can turn self-loops into longer cycles. A lower coNP-complete complexity bound can be obtained if we require that all self-loops in the poNFA are deterministic, in the sense that the symbol read in the loop cannot occur in any other transition from that state. We find that such restricted poNFAs (rpoNFAs) characterise the class of $mathcalR$-trivial languages, and we establish the complexity of deciding if the language of an NFA is $mathcalR$-trivial. Nevertheless, the limitation to fixed alphabets turns out to be essential even in the restricted case: deciding universality of rpoNFAs with unbounded alphabets is PSPACE-complete. Based on a close relation between universality and the problems of inclusion and equivalence, we also obtain the complexity results for these two problems. Finaly, we show that the languages of rpoNFAs are definable by deterministic (one-unambiguous) regular expressions, which makes them interesting in schema languages for XML data.

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

Recommendations

• On the complexity of universality for partially ordered NFAs
• Deciding Universality of ptNFAs is PSpace-Complete
• The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages
• The parallel complexity of finite-state automata problems
• On NFAs where all states are final, initial, or both

zbMATH Keywords

equivalencepartial orderautomatanondeterminismuniversalityinclusion

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Deciding definability by deterministic regular expressions
• One-unambiguous regular languages
• On the computational power of pushdown automata
• Complexity of decision problems for XML schemas and chain regular expressions
• Querying regular graph patterns
• Title not available (Why is that?)
• Regular expressions: new results and open problems
• A generalization of the Schützenberger product of finite monoids
• Classification of finite monoids: the language approach
• Finite semigroup varieties of the form V*D
• Languages of dot-depth 3/2
• Dot-depth of star-free events
• Descriptional and computational complexity of finite automata -- a survey
• The inclusion problem for simple languages
• Permutation rewriting and algorithmic verification
• Around dot depth two
• Space-bounded reducibility among combinatorial problems
• Sur le produit de concatenation non ambigu
• Title not available (Why is that?)
• Computational Parallels between the Regular and Context-Free Languages
• Languages of R-trivial monoids
• The dot-depth hierarchy of star-free languages is infinite
• Machines, Computations, and Universality
• The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages
• The equivalence problem for deterministic pushdown automata is decidable
• On decidability of intermediate levels of concatenation hierarchies
• Title not available (Why is that?)
• Separation and the successor relation
• Piecewise testable languages and nondeterministic automata
• Alternative automata characterization of piecewise testable languages
• Separability by short subsequences and subwords
• On Boolean combinations forming piecewise testable languages
• The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases
• Partially ordered two-way Büchi automata
• On the complexity of universality for partially ordered NFAs
• Separating regular languages with two quantifiers alternations

Cited In (12)

• Constrained synchronization and subset synchronization problems for weakly acyclic automata
• Deciding Universality of ptNFAs is PSpace-Complete
• State complexity of permutation and related decision problems on alphabetical pattern constraints
• On the complexity of universality for partially ordered NFAs
• Complexity of deciding detectability in discrete event systems
• On verification of D-detectability for discrete event systems
• Absent Subsequences in Words
• Matching patterns with variables under Simon's congruence
• Title not available (Why is that?)
• Scattered Factor-Universality of Words
• #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
• State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs

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

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