enter search term and/or author name
Automatic linear orders and trees
Bakhadyr Khoussainov, Sasha Rubin, Frank Stephan
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
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
The degree sequence of an n-vertex graph is d
A proof theory for generic judgments
Dale Miller, Alwen Tiu
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
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...