Partially ordered automata and piecewise testability

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

A generalization of the Schützenberger product of finite monoids
A note on partially ordered tree automata
A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
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
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?)
Languages of dot-depth 3/2
Languages of R-trivial monoids
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

(10)

Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order
On verification of D-detectability for discrete event systems
State complexity of permutation and related decision problems on alphabetical pattern constraints
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
Subset mapping problems in solvable automata
On algorithms verifying initial-and-final-state opacity: complexity, special cases, and comparison
Co-lexicographically ordering automata and regular languages. I
Monoids of upper triangular matrices over the Boolean semiring

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)