Partially ordered automata and piecewise testability
From MaRDI portal
Publication:4989409
Authors: Tomáš Masopust, Markus Krötzsch 
Publication date: 25 May 2021
Full work available at URL: https://arxiv.org/abs/1907.13115
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complexity of decision problems for XML schemas and chain regular expressions
- Title not available (Why is that?)
- Querying regular graph patterns
- Title not available (Why is that?)
- On the structure of semigroups
- Linear reasoning. A new form of the Herbrand-Gentzen theorem
- 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
- Polynomial closure and unambiguous product
- Finite semigroup varieties of the form V*D
- Languages of dot-depth 3/2
- Dot-depth of star-free events
- On separation by locally testable and locally threshold testable languages
- Efficient separability of regular languages by subsequences and suffixes
- Finite-automaton aperiodicity is PSPACE-complete
- Observability of discrete event dynamic systems
- The complementation problem for Büchi automata with applications to temporal logic
- Weak alternating automata are not that weak
- Finite automata and unary languages
- Modelling opacity using Petri nets
- Opacity of discrete event systems and its applications
- The inclusion problem for simple languages
- Permutation rewriting and algorithmic verification
- A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
- Around dot depth two
- Detectability of Discrete Event Systems
- Space-bounded reducibility among combinatorial problems
- Generalized detectability for discrete event systems
- Sur le produit de concatenation non ambigu
- Piecewise testable tree languages
- The Common Fragment of ACTL and LTL
- Complexity of deciding detectability in discrete event systems
- Title not available (Why is that?)
- Constraint solving for interpolation
- The covering problem
- Languages of R-trivial monoids
- The dot-depth hierarchy of star-free languages is infinite
- Supervisory control and reactive synthesis: a comparative introduction
- Title not available (Why is that?)
- Alternating automata, the weak monadic theory of trees and its complexity
- Coordination control of discrete-event systems revisited
- Complexity of universality and related problems for partially ordered NFAs
- Alternation Elimination by Complementation (Extended Abstract)
- A note on partially ordered tree automata
- The equivalence problem for deterministic pushdown automata is decidable
- Separating regular languages with two quantifier alternations
- On decidability of intermediate levels of concatenation hierarchies
- Title not available (Why is that?)
- Computation of controllable and coobservable sublanguages in decentralized supervisory control via communication
- Separability by piecewise testable languages is \textsc{PTime}-complete
- 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
- Complexity of detectability, opacity and A-diagnosability for modular discrete event systems
- The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases
- Partially ordered two-way Büchi automata
- Evaluation and enumeration problems for regular path queries
- Separating regular languages with two quantifiers alternations
- Title not available (Why is that?)
- The power of programs over monoids in DA
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
- Title not available (Why is that?)
- 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)
