ACM DL

Computational Logic (TOCL)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Computational Logic (TOCL), Volume 3 Issue 3, July 2002

Editorial
Martín Abadi, Leonid Libkin, Frank Pfenning
Pages: 335-335
DOI: 10.1145/507382.507383
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
Pages: 336-358
DOI: 10.1145/507382.507384
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
Pages: 359-382
DOI: 10.1145/507382.507385
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
Pages: 383-401
DOI: 10.1145/507382.507386
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
Pages: 402-417
DOI: 10.1145/507382.507387
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
Pages: 418-463
DOI: 10.1145/507382.507388
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...