Complexity of universality and related problems for partially ordered NFAs
From MaRDI portal
Publication:2013561
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 -trivial languages, and we establish the complexity of deciding if the language of an NFA is -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
- 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
- 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?)
- Languages of dot-depth 3/2
- Languages of R-trivial monoids
- 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
(20)- 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
- On the complexity of universality for partially ordered NFAs
- Partially ordered automata and piecewise testability
- Scattered Factor-Universality of Words
- #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
- Deciding Universality of ptNFAs is PSpace-Complete
- 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
- Matching patterns with variables under Simon's congruence
- k-universality of regular languages
- Relative densities of formal languages
- Subset mapping problems in solvable automata
- On algorithms verifying initial-and-final-state opacity: complexity, special cases, and comparison
- The edit distance to k-subsequence universality
- \(k\)-universality of regular languages
- The edit distance to \(k\)-subsequence universality
- Monoids of upper triangular matrices over the Boolean semiring
- Constrained synchronization and subset synchronization problems for weakly acyclic automata
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)
