Partially ordered automata and piecewise testability
From MaRDI portal
Publication:4989409
Recommendations
- Deciding Universality of ptNFAs is PSpace-Complete
- On the complexity of universality for partially ordered NFAs
- Complexity of universality and related problems for partially ordered NFAs
- Piecewise testable languages and nondeterministic automata
- On the complexity of \(k\)-piecewise testability and the depth of automata
Cites work
- scientific article; zbMATH DE number 3930354 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (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 1775408 (Why is no real title available?)
- scientific article; zbMATH DE number 2087227 (Why is no real title available?)
- scientific article; zbMATH DE number 1839456 (Why is no real title available?)
- scientific article; zbMATH DE number 5585443 (Why is no real title available?)
- scientific article; zbMATH DE number 7056230 (Why is no real title available?)
- A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
- A generalization of the Schützenberger product of finite monoids
- A note on partially ordered tree automata
- Alternating automata, the weak monadic theory of trees and its complexity
- Alternation Elimination by Complementation (Extended Abstract)
- Alternative automata characterization of piecewise testable languages
- Around dot depth two
- Classification of finite monoids: the language approach
- Complexity of deciding detectability in discrete event systems
- Complexity of decision problems for XML schemas and chain regular expressions
- Complexity of detectability, opacity and A-diagnosability for modular discrete event systems
- Complexity of universality and related problems for partially ordered NFAs
- Computation of controllable and coobservable sublanguages in decentralized supervisory control via communication
- Constraint solving for interpolation
- Coordination control of discrete-event systems revisited
- Detectability of Discrete Event Systems
- Dot-depth of star-free events
- Efficient separability of regular languages by subsequences and suffixes
- Evaluation and enumeration problems for regular path queries
- Finite automata and unary languages
- Finite semigroup varieties of the form V*D
- Finite-automaton aperiodicity is PSPACE-complete
- Generalized detectability for discrete event systems
- Languages of R-trivial monoids
- Languages of dot-depth 3/2
- Linear reasoning. A new form of the Herbrand-Gentzen theorem
- Modelling opacity using Petri nets
- Observability of discrete event dynamic systems
- On Boolean combinations forming piecewise testable languages
- On decidability of intermediate levels of concatenation hierarchies
- On separation by locally testable and locally threshold testable languages
- On the structure of semigroups
- Opacity of discrete event systems and its applications
- Partially ordered two-way Büchi automata
- Permutation rewriting and algorithmic verification
- Piecewise testable languages and nondeterministic automata
- Piecewise testable tree languages
- Polynomial closure and unambiguous product
- Querying regular graph patterns
- Regular expressions: new results and open problems
- Separability by piecewise testable languages is \textsc{PTime}-complete
- Separability by short subsequences and subwords
- Separating regular languages with two quantifier alternations
- Separating regular languages with two quantifiers alternations
- Separation and the successor relation
- Space-bounded reducibility among combinatorial problems
- Supervisory control and reactive synthesis: a comparative introduction
- Sur le produit de concatenation non ambigu
- The Common Fragment of ACTL and LTL
- The complementation problem for Büchi automata with applications to temporal logic
- The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases
- The covering problem
- 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
- The power of programs over monoids in DA
- Weak alternating automata are not that weak
Cited in
(6)- State complexity of permutation and related decision problems on alphabetical pattern constraints
- On verification of D-detectability for discrete event systems
- Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order
- Piecewise directable automata
- scientific article; zbMATH DE number 4155920 (Why is no real title available?)
- 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: Partially ordered automata and piecewise testability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4989409)
