Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 52 Issue 6, November 2005

Time-space lower bounds for satisfiability
Lance Fortnow, Richard Lipton, Dieter van Melkebeek, Anastasios Viglas
Pages: 835-865
DOI: 10.1145/1101821.1101822
We establish the first polynomial time-space lower bounds for satisfiability on general models of computation. We show that for any constant c less than the golden ratio there exists a positive constant d such that no deterministic...

Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Pages: 866-893
DOI: 10.1145/1101821.1101823
We introduce a new framework for designing fixed-parameter algorithms with subexponential running time---2O(&kradic;) nO(1). Our results apply to a broad family of graph problems, called bidimensional...

Ownership confinement ensures representation independence for object-oriented programs
Anindya Banerjee, David A. Naumann
Pages: 894-960
DOI: 10.1145/1101821.1101824
Representation independence formally characterizes the encapsulation provided by language constructs for data abstraction and justifies reasoning by simulation. Representation independence has been shown for a variety of languages and constructs but...

Behavioral theory for mobile ambients
Massimo Merro, Francesco Zappa Nardelli
Pages: 961-1023
DOI: 10.1145/1101821.1101825
We study a behavioral theory of Mobile Ambients, a process calculus for modelling mobile agents in wide-area networks, focussing on reduction barbed congruence. Our contribution is threefold. (1) We prove a context lemma which...