Complexity of universality and related problems for partially ordered NFAs

DOI10.1016/J.IC.2017.06.004MaRDI QIDQ2013561zbMATH OpenOpenAlexFDO

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

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

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)

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.

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

Cites work

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

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
• scientific article; zbMATH DE number 7350780 (Why is no real title available?)
• 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)