ACM DL

Computational Logic (TOCL)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Computational Logic (TOCL), Volume 6 Issue 4, October 2005

Editorial
Krzysztof R. Apt
Pages: 673-673
DOI: 10.1145/1094622.1094623

LICS 2003 special issue
Phokion G. Kolaitis
Pages: 674-674
DOI: 10.1145/1094622.1094624

Automatic linear orders and trees
Bakhadyr Khoussainov, Sasha Rubin, Frank Stephan
Pages: 675-700
DOI: 10.1145/1094622.1094625
We investigate partial orders that are computable, in a precise sense, by finite automata. Our emphasis is on trees and linear orders. We study the relationship between automatic linear orders and trees in terms of rank functions that are related to...

About the undecidability of program equivalence in finitary languages with state
Andrzej S. Murawski
Pages: 701-726
DOI: 10.1145/1094622.1094626
We show how game semantics can be employed to prove that program equivalence in finitary Idealized Algol with active expressions is undecidable. We also investigate a notion of representability of languages by terms and show that finitary Idealized...

Convergence law for random graphs with specified degree sequence
James F. Lynch
Pages: 727-748
DOI: 10.1145/1094622.1094627
The degree sequence of an n-vertex graph is d0,…,dn−1, where each di is the number of vertices of degree i in the graph. A random graph with degree...

A proof theory for generic judgments
Dale Miller, Alwen Tiu
Pages: 749-783
DOI: 10.1145/1094622.1094628
The operational semantics of a computation system is often presented as inference rules or, equivalently, as logical theories. Specifications can be made more declarative and high level if syntactic details concerning bound variables and...

Proof nets for unit-free multiplicative-additive linear logic
Dominic J. D. Hughes, Rob J. Van Glabbeek
Pages: 784-842
DOI: 10.1145/1094622.1094629
A cornerstone of the theory of proof nets for unit-free multiplicative linear logic (MLL) is the abstract representation of cut-free proofs modulo inessential rule commutation. The only known extension to additives, based on monomial weights, fails...