Results 61 to 70 of about 43,821 (313)
Asynchronous wreath product and cascade decompositions for concurrent behaviours [PDF]
Logical Methods in Computer Science, 2022 We develop new algebraic tools to reason about concurrent behaviours modelled as languages of Mazurkiewicz traces and asynchronous automata. These tools reflect the distributed nature of traces and the underlying causality and concurrency between events,
Bharat Adsul +3 more
doaj +1 more source
Satisfiability Games for Branching-Time Logics [PDF]
, 2013 The satisfiability problem for branching-time temporal logics like CTL*, CTL and CTL+ has important applications in program specification and verification. Their computational complexities are known: CTL* and CTL+ are complete for doubly exponential time,
Friedmann, Oliver +2 more
core +2 more sources
Logical Methods in Computer Science, 2020 We introduce a class of algebras that can be used as recognisers for regular tree languages. We show that it is the only such class that forms a pseudo-variety and we prove the existence of syntactic algebras.
Achim Blumensath
doaj +1 more source
Completeness Theorems for Kleene algebra with tests and top [PDF]
Logical Methods in Computer ScienceWe prove two completeness results for Kleene algebra with tests and a top element, with respect to guarded string languages and binary relations. While the equational theories of those two classes of models coincide over the signature of Kleene algebra ...
Damien Pous, Jana Wagemaker
doaj +1 more source
Structural Reductions and Stutter Sensitive Properties [PDF]
Logical Methods in Computer ScienceVerification of properties expressed as $\omega$-regular languages such as LTL can benefit hugely from stutter insensitivity, using a diverse set of reduction strategies.
Emmanuel Paviot-Adet +3 more
doaj +1 more source
Quantitative Automata under Probabilistic Semantics [PDF]
Logical Methods in Computer Science, 2019 Automata with monitor counters, where the transitions do not depend on counter values, and nested weighted automata are two expressive automata-theoretic frameworks for quantitative properties. For a well-studied and wide class of quantitative functions,
Krishnendu Chatterjee +2 more
doaj +1 more source
Constructing Concise Characteristic Samples for Acceptors of Omega Regular Languages [PDF]
Logical Methods in Computer ScienceA characteristic sample for a language $L$ and a learning algorithm $\textbf{L}$ is a finite sample of words $T_L$ labeled by their membership in $L$ such that for any sample $T \supseteq T_L$ consistent with $L$, on input $T$ the learning algorithm ...
Dana Angluin, Dana Fisman
doaj +1 more source
Unifying B\"uchi Complementation Constructions [PDF]
Logical Methods in Computer Science, 2013 Complementation of B\"uchi automata, required for checking automata containment, is of major theoretical and practical interest in formal verification. We consider two recent approaches to complementation.
Seth J. Fogarty +3 more
doaj +1 more source
Graph Logics with Rational Relations [PDF]
Logical Methods in Computer Science, 2013 We investigate some basic questions about the interaction of regular and rational relations on words. The primary motivation comes from the study of logics for querying graph topology, which have recently found numerous applications.
Pablo Barcelo +2 more
doaj +1 more source
Regular Cost Functions, Part I: Logic and Algebra over Words [PDF]
Logical Methods in Computer Science, 2013 The theory of regular cost functions is a quantitative extension to the classical notion of regularity. A cost function associates to each input a non-negative integer value (or infinity), as opposed to languages which only associate to each input the ...
Thomas Colcombet
doaj +1 more source