Results 61 to 70 of about 43,033 (311)
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
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
Characterizations of recognizable picture series [PDF]
, 1935 The theory of two-dimensional languages as a generalization of formal string languages was motivated by problems arising from image processing and pattern recognition, and also concerns models of parallel computing.
Mäurer, Ina
core +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
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
Automatic functions, linear time and learning [PDF]
Logical Methods in Computer Science, 2013 The present work determines the exact nature of {\em linear time computable} notions which characterise automatic functions (those whose graphs are recognised by a finite automaton). The paper also determines which type of linear time notions permit full
John Case +3 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
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