enter search term and/or author name
Time-space lower bounds for satisfiability
Lance Fortnow, Richard Lipton, Dieter van Melkebeek, Anastasios Viglas
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
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
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
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...