Results 21 to 30 of about 1,138,378 (107)
QRB-Domains and the Probabilistic Powerdomain [PDF]
Logical Methods in Computer Science, 2012 Is there any Cartesian-closed category of continuous domains that would be closed under Jones and Plotkin's probabilistic powerdomain construction? This is a major open problem in the area of denotational semantics of probabilistic higher-order languages.
Jean Goubault-Larrecq
doaj +1 more source
A lower bound on web services composition [PDF]
Logical Methods in Computer Science, 2008 A web service is modeled here as a finite state machine. A composition problem for web services is to decide if a given web service can be constructed from a given set of web services; where the construction is understood as a simulation of the ...
Anca Muscholl, Igor Walukiewicz
doaj +1 more source
Randomisation and Derandomisation in Descriptive Complexity Theory [PDF]
Logical Methods in Computer Science, 2011 We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic L we introduce a new logic BPL, bounded error probabilistic L, which is defined from L in a similar way as the complexity class BPP ...
Kord Eickmeyer, Martin Grohe
doaj +1 more source
Interactive Small-Step Algorithms I: Axiomatization [PDF]
Logical Methods in Computer Science, 2007 In earlier work, the Abstract State Machine Thesis -- that arbitrary algorithms are behaviorally equivalent to abstract state machines -- was established for several classes of algorithms, including ordinary, interactive, small-step algorithms.
Andreas Blass +3 more
doaj +1 more source
Weighted Logics for Nested Words and Algebraic Formal Power Series [PDF]
Logical Methods in Computer Science, 2010 Nested words, a model for recursive programs proposed by Alur and Madhusudan, have recently gained much interest. In this paper we introduce quantitative extensions and study nested word series which assign to nested words elements of a semiring. We show
Christian Mathissen
doaj +1 more source
Build your own clarithmetic I: Setup and completeness [PDF]
Logical Methods in Computer Science, 2017 Clarithmetics are number theories based on computability logic (see http://www.csc.villanova.edu/~japaridz/CL/ ). Formulas of these theories represent interactive computational problems, and their "truth" is understood as existence of an algorithmic ...
Giorgi Japaridze
doaj +1 more source
Hyper Normalisation and Conditioning for Discrete Probability Distributions [PDF]
Logical Methods in Computer Science, 2017 Normalisation in probability theory turns a subdistribution into a proper distribution. It is a partial operation, since it is undefined for the zero subdistribution. This partiality makes it hard to reason equationally about normalisation.
Bart Jacobs
doaj +1 more source
Visibly Tree Automata with Memory and Constraints [PDF]
Logical Methods in Computer Science, 2008 Tree automata with one memory have been introduced in 2001. They generalize both pushdown (word) automata and the tree automata with constraints of equality between brothers of Bogaert and Tison.
Hubert Comon-Lundh +2 more
doaj +1 more source
On Global Types and Multi-Party Session [PDF]
Logical Methods in Computer Science, 2012 Global types are formal specifications that describe communication protocols in terms of their global interactions. We present a new, streamlined language of global types equipped with a trace-based semantics and whose features and restrictions are ...
Giuseppe Castagna +2 more
doaj +1 more source
Some theorems on passing from local to global presence of properties of functions [PDF]
Logical Methods in Computer Science, 2017 When given a class of functions and a finite collection of sets, one might be interested whether the class in question contains any function whose domain is a subset of the union of the sets of the given collection and whose restrictions to all of them ...
Dimiter Skordev
doaj +1 more source