Results 41 to 50 of about 1,681 (204)
Logical properties of random graphs from small addable classes [PDF]
Logical Methods in Computer Science, 2019 We establish zero-one laws and convergence laws for monadic second-order logic (MSO) (and, a fortiori, first-order logic) on a number of interesting graph classes.
Anuj Dawar, Eryk Kopczyński
doaj +1 more source
Logics with rigidly guarded data tests [PDF]
Logical Methods in Computer Science, 2015 The notion of orbit finite data monoid was recently introduced by Bojanczyk as an algebraic object for defining recognizable languages of data words.
Gabriele Puppis +2 more
doaj +1 more source
On Supergraphs Satisfying CMSO Properties [PDF]
Logical Methods in Computer Science, 2021 Let CMSO denote the counting monadic second order logic of graphs. We give a constructive proof that for some computable function $f$, there is an algorithm $\mathfrak{A}$ that takes as input a CMSO sentence $\varphi$, a positive integer $t$, and a ...
Mateus de Oliveira Oliveira
doaj +1 more source
Logic and Branching Automata [PDF]
Logical Methods in Computer Science, 2015 In this paper we study the logical aspects of branching automata, as defined by Lodaya and Weil. We first prove that the class of languages of finite N-free posets recognized by branching automata is closed under complementation.
Bedon Nicolas
doaj +1 more source
A Curry-Howard Approach to Church's Synthesis [PDF]
Logical Methods in Computer Science, 2019 Church's synthesis problem asks whether there exists a finite-state stream transducer satisfying a given input-output specification. For specifications written in Monadic Second-Order Logic (MSO) over infinite words, Church's synthesis can theoretically ...
Pierre Pradic, Colin Riba
doaj +1 more source
Typing weak MSOL properties [PDF]
Logical Methods in Computer Science, 2017 We consider lambda-Y-calculus as a non-interpreted functional programming language: the result of the execution of a program is its normal form that can be seen as the tree of calls to built-in operations.
Sylvain Salvati, Igor Walukiewicz
doaj +1 more source
Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure [PDF]
Logical Methods in Computer Science, 2007 String languages recognizable in (deterministic) log-space are characterized either by two-way (deterministic) multi-head automata, or following Immerman, by first-order logic with (deterministic) transitive closure.
Joost Engelfriet, Hendrik Jan Hoogeboom
doaj +1 more source
On the completeness and the decidability of strictly monadic second‐order logic
Mathematical Logic Quarterly, 2020 AbstractRegarding strictly monadic second‐order logic (SMSOL), which is the fragment of monadic second‐order logic in which all predicate constants are unary and there are no function symbols, we show that a standard deductive system with full comprehension is sound and complete with respect to standard semantics.
Kento Takagi, Ryo Kashima
openaire +3 more sources
Logical and Algebraic Characterizations of Rational Transductions [PDF]
Logical Methods in Computer Science, 2019 Rational word languages can be defined by several equivalent means: finite state automata, rational expressions, finite congruences, or monadic second-order (MSO) logic.
Emmanuel Filiot +2 more
doaj +1 more source
Quantified CTL: Expressiveness and Complexity [PDF]
Logical Methods in Computer Science, 2014 While it was defined long ago, the extension of CTL with quantification over atomic propositions has never been studied extensively. Considering two different semantics (depending whether propositional quantification refers to the Kripke structure or to ...
François Laroussinie, Nicolas Markey
doaj +1 more source