Results 51 to 60 of about 46,330 (328)
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
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
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
A B\"uchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 We introduce MSO graph storage types, and call a storage type MSO-expressible if it is isomorphic to some MSO graph storage type. An MSO graph storage type has MSO-definable sets of graphs as storage configurations and as storage transformations.
Joost Engelfriet, Heiko Vogler
doaj +1 more source
A Theory of Formal Choreographic Languages [PDF]
Logical Methods in Computer Science, 2023 We introduce a meta-model based on formal languages, dubbed formal choreographic languages, to study message-passing systems. Our framework allows us to generalise standard constructions from the literature and to compare them. In particular, we consider
Franco Barbanera +2 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
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
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