scientific article; zbMATH DE number 7350780

MaRDI QIDQ4989409FDOQ4989409

Authors: Tomáš Masopust, Markus Krötzsch 

Publication date: 25 May 2021

Full work available at URL: https://arxiv.org/abs/1907.13115

Title of this publication is not available (Why is that?)

zbMATH Keywords

complexityautomatanondeterminism

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Alternative Automata Characterization of Piecewise Testable Languages
• Title not available (Why is that?)
• 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:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4989409)