Results 1 to 10 of about 836,741 (199)
Linear equations for unordered data vectors in $[D]^k\to{}Z^d$ [PDF]
Logical Methods in Computer Science, 2022 Following a recently considered generalisation of linear equations to unordered-data vectors and to ordered-data vectors, we perform a further generalisation to data vectors that are functions from k-element subsets of the unordered-data set to vectors ...
Piotr Hofman, Jakub Różycki
doaj +1 more source
Combinatorial Conversion and Moment Bisimulation for Stochastic Rewriting Systems [PDF]
Logical Methods in Computer Science, 2020 We develop a novel method to analyze the dynamics of stochastic rewriting systems evolving over finitary adhesive, extensive categories. Our formalism is based on the so-called rule algebra framework and exhibits an intimate relationship between the ...
Nicolas Behr +2 more
doaj +1 more source
Certified Context-Free Parsing: A formalisation of Valiant's Algorithm in Agda [PDF]
Logical Methods in Computer Science, 2016 Valiant (1975) has developed an algorithm for recognition of context free languages. As of today, it remains the algorithm with the best asymptotic complexity for this purpose.
Jean-Philippe Bernardy, Patrik Jansson
doaj +1 more source
On properties of $B$-terms [PDF]
Logical Methods in Computer Science, 2020 $B$-terms are built from the $B$ combinator alone defined by $B\equiv\lambda fgx. f(g~x)$, which is well known as a function composition operator.
Mirai Ikebuchi, Keisuke Nakano
doaj +1 more source
Termination of Rewriting with Right-Flat Rules Modulo Permutative Theories [PDF]
Logical Methods in Computer Science, 2010 We present decidability results for termination of classes of term rewriting systems modulo permutative theories. Termination and innermost termination modulo permutative theories are shown to be decidable for term rewrite systems (TRS) whose right-hand ...
Luis Barguno +3 more
doaj +1 more source
Termination of Cycle Rewriting by Transformation and Matrix Interpretation [PDF]
Logical Methods in Computer Science, 2017 We present techniques to prove termination of cycle rewriting, that is, string rewriting on cycles, which are strings in which the start and end are connected.
David Sabel, Hans Zantema
doaj +1 more source
Rule Algebras for Adhesive Categories [PDF]
Logical Methods in Computer Science, 2020 We demonstrate that the most well-known approach to rewriting graphical structures, the Double-Pushout (DPO) approach, possesses a notion of sequential compositions of rules along an overlap that is associative in a natural sense.
Nicolas Behr, Pawel Sobocinski
doaj +1 more source
Complexity of Conditional Term Rewriting [PDF]
Logical Methods in Computer Science, 2017 We propose a notion of complexity for oriented conditional term rewrite systems satisfying certain restrictions. This notion is realistic in the sense that it measures not only successful computations, but also partial computations that result in a ...
Cynthia Kop +2 more
doaj +1 more source
Infinitary Combinatory Reduction Systems: Normalising Reduction Strategies [PDF]
Logical Methods in Computer Science, 2010 We study normalising reduction strategies for infinitary Combinatory Reduction Systems (iCRSs). We prove that all fair, outermost-fair, and needed-fair strategies are normalising for orthogonal, fully-extended iCRSs.
Jeroen Ketema, Jakob Grue Simonsen
doaj +1 more source
Coherent Presentations of Monoidal Categories [PDF]
Logical Methods in Computer Science, 2017 Presentations of categories are a well-known algebraic tool to provide descriptions of categories by means of generators, for objects and morphisms, and relations on morphisms.
Pierre-Louis Curien, Samuel Mimram
doaj +1 more source