enter search term and/or author name
Martín Abadi, Leonid Libkin, Frank Pfenning
This special issue of ACM Transactions on Computational Logic is devoted to papers first presented at LICS 2000, the 15th Annual IEEE Symposium on Logic in Computer Science, held June 26--29, 2000, in Santa Barbara, California.In consultation...
On first-order topological queries
Martin Grohe, Luc Segoufin
One important class of spatial database queries is the class of topological queries, that is, queries invariant under homeomorphisms. We study topological queries expressible in the standard query language on spatial databases, first-order...
Probabilistic game semantics
Vincent Danos, Russell S. Harmer
A category of HO/N-style games and probabilistic strategies is developed where the possible choices of a strategy are quantified so as to give a measure of the likelihood of seeing a given play. A two-sided die is shown to be universal in this...
A syntactical analysis of non-size-increasing polynomial time computation
Klaus Aehlig, Helmut Schwichtenberg
A syntactical proof is given that all functions definable in a certain affine linear typed λ-calculus with iteration in all types are polynomial time computable. The proof provides explicit polynomial bounds that can easily be calculated.
Resource-bounded continuity and sequentiality for type-two functionals
Samuel R. Buss, Bruce M. Kapron
We define notions of resource-bounded continuity and sequentiality for type-two functionals with total inputs, and prove that in the resource-bounded model there are continuous functionals which cannot be efficiently simulated by sequential...
Back and forth between guarded and modal logics
Erich Grädel, Colin Hirsch, Martin Otto
Guarded fixed-point logic μGF extends the guarded fragment by means of least and greatest fixed points, and thus plays the same role within the domain of guarded logics as the modal μ-calculus plays within the modal domain. We provide a...