Accepted Conference Papers

List of Events:

RTA 2005
International Conference on Rewriting Techniques and Applications
Nara, Japan, April 19-21, 2005

The International Conference on Rewriting Techniques and Applications (RTA) is the major conference on rewriting. Its creation was decided after the Workshop on the Rewrite Rule Laboratory, held in Schenectady (NY) in September 1983. From 1985 to 1993, RTA was a bi-annual conference. In 1995, RTA was merged with the Workshop on Conditional (and Typed) Term Rewriting Systems (CTRS) and became an annual conference.

Accepted Papers

Constraint Solving and Programming
track at ACM Symposium on Applied Computing
Santa Fe, New Mexico, March 13-17, 2005

The track is concerned with all aspects of computing with constraints including algorithms, applications, environments, languages, models, and systems. Contributions are welcome from any discipline concerned with constraints, including artificial intelligence, combinatorial algorithms, computational logic, concurrent computation, databases, discrete mathematics, operations research, programming languages, and symbolic computation. We also solicit papers from any domain employing constraints, including computational linguistics, configuration, decision support, design, diagnosis, graphics, hardware verification, molecular biology, planning, qualitative reasoning, real-time systems, resource allocation, robotics, scheduling, software engineering, temporal reasoning, vision, visualization, and user interfaces. Papers that bridge disciplines or combine theory and practice or discuss novel reasoning methods are especially welcome. A special attention is focused around the use of constraint technologies in the networking, wireless and internet fields.

List of Accepted Papers
Limited Assignments: A New Cutoff Strategy for Incomplete Depth-First Search
Roman Bartak, Hana Rudova
On the Computational limits of Infinite Satisfaction
Stefan Dantchev, Frank D. Valencia
Breaking Value Symmetries in Matrix Models using Channeling Constraints
Y.C. Law, J.H.M. Lee
Hybrid Lagrangian Relaxation for Bandwidth-Constrained Routing: Knapsack Decomposition
Wided Ouaja, Barry Richards
A Branch-Price-and-Propagate Approach for Optimising IGP Weight Setting subject to Unique Shortest Paths
Farid Ajili, Robert Rodosek, Andrew Eremin
Solving Strategies using a Hybridization Model for Local Search and Constraint Propagation
Tony Lambert, Eric Monfroy, F. Saubion
Controlled Propagation in Continuous Numerical Constraint Networks
Frédéric Goualard, Laurent Granvilliers
Timid Acquisition of Constraint Satisfaction Problems
Sarah O'Connell, Barry O'Sullivan and Eugene C. Freuder

International Conference on Automated Planning and Scheduling
Monterey, California, June 5-10, 2005

The  International Conference on Automated Planning & Scheduling (ICAPS)  is the premier forum for researchers and practitioners in Intelligent  Planning & Scheduling and related fields. Topics include all aspects of planning and scheduling theory and practice, including a wide spectrum of applications. The ICAPS 2005 main conference will be accompanied by a  program of tutorials and workshops, a doctoral consortium, and demonstrations of planning and scheduling systems. As a novelty, the first International  Competition on Knowledge Engineering for Planning will be held at the conference.

ICAPS 2005 will be take place in Monterey, California, U.S.A. between June 5 and 10 at the Hyatt Regency Monterey Resort and Conference Center

List of Accepted Papers


On the Tractability of Restricted Disjunctive Temporal Problems

T. K. Satish Kumar, Stanford University, USA

Improving Parallel Planning with Constraints on the Number of Operators

Markus Buttner, Jussi Rintanen, Albert-Ludwigs-Universitaet Freiburg, Germany

Planning with Goal Preferences and Constraints

Ronen Brafman, Yuri Chernyavsky, NASA Ames Research Center & Stanford University, USA

External Symbolic Heursitic Search with Pattern Databases

Stefan Edelkamp, University of Dortmund, Germany

Genetic Planning Using Variable Length Chromosomes

Alexandre Brie, Philippe Morignot, Ecole Polytechnique Palaiseau, France

Characterizing the Distribution of Low-Makespan Schedules in the Job Shop Scheduling Problem

Matthew Streeter, Stephen Smith, Carnegie Mellon University, USA

Planning Graph Heuristics for Selecting Objectives in Over-subscription Planning Problems

Romeo Sanchez, Subbarao Kambhampati, Arizona State University, USA

Contingent Planning via Heuristic Forward Search with Implicit Belief States

Joerg Hoffmann, Ronen Brafman, Max-Planck-Institut fuer Informatik Saarbruecken, Germany

Concurrent Probabilistic Temporal Planning

Mausam, Daniel Weld, University of Washington, USA

Automated Composition of Web Services by Planning in Asynchronous Domains

Marco Pistore, Paolo Traverso, Piergiorgio Bertoli, University of Trento, Italy

Anytime Dynamic A*: An Anytime, Replanning Algorithm

Maxim Likhachev, David Ferguson, Geoff Gordon, Anthony Stentz, Sebastian Thrun, Carnegie Mellon University, USA

The Yoyo Planner: Going Where Hierarchical Task-Network Planning Meets With Symbolic Model Checking

Ugur Kuter, Dana Nau, Marco Pistore, Paolo Traverso, University of Maryland, USA

Plan Repair as an Extension of Planning

Roman van der Krogt, Mathijs de Weerdt, Delft University of Technology, Netherlands

Randomized Large Neighborhood Search for Cumulative Scheduling

Daniel Godard, Philippe Laborie, Wim Nuitjen, ILOG, France

Minimizing Breaks in Sport Scheduling with Local Search

Pascal van Hentenryck, Yannis Vergados, Brown University, USA

Online Stochastic Optimization Without Distributions

Pascal van Hentenryck, Russell Bent, Brown University, USA

Learning Partial-Order Macros from Solutions

Adi Botea, Martin Mueller, Jonathan Schaeffer, University of Alberta, Canada

Search Control in Planning for Temporally Extended Goals

Froduald Kabanza, Sylvie Thiebaux, Universite de Sherbrooke, Canada

Activity Planning for the Mars Exploration Rovers

John Bresina, Ari Jonsson, Paul Morris, Kanna Rajan, NASA Ames Research Center, USA

Reviving Integer Programming Approaches for AI Planning: A Branch-and-Cut Framework

Menkes van den Briel, Thomas Vossen, Subbarao Kambhampati, Arizona State University, USA

Solving Over-constrained DTPs with Preferences

Bart Peintner, Michael Moffitt, Martha Pollack, University of Michigan, USA

Pruning Conformant Plans by Counting Models on Compiled d-DNNF Representations

Hector Palacios, Blai Bonet, Adnan Darwiche, Hector Geffner, Universitat Pompeu Fabra, Spain

On-line Planning and Scheduling for High-speed Manufacturing

Wheeler Ruml, Minh Do, Markus Fromherz, Palo Alto Research Center, USA

Learning Action Models from Plan Examples with Incomplete Knowledge

Qiang Yang, K. Wu, Y. Jiang, Hong Kong University of Science and Technology, China

Course of Action Generation for Cyber Security Using Classical Planning

Mark Boddy, Tom Haigh, Johnathan Gohde, Steven Harp, Adventium Labs, USA

Retaining Flexibility to Maximize Quality: When the Scheduler Has the Right to Decide Activity Duration

Xiaofang Wang, Stephen Smith, Carnegie Mellon University, USA

Maximizing Availability: A Commitment Heuristic for Oversubscribed Scheduling Problems

Laurence Kramer, Stephen Smith, Carnegie Mellon University, USA

A Generalized Framework for Lifelong Planning A*

Maxim Likhachev, Sven Koenig, Carnegie Mellon University, USA

Fast Exact Planning in Markov Decision Processes

H. Brendan McMahan, Geoff Gordon, Carnegie Mellon University, USA

Beam-Stack Search: Integrating Backtracking with Beam Search

Rong Zhou, Eric Hansen, Mississippi State University, USA

Enabling Fast Flexible Planning through Incremental Temporal Reasoning with Conflict Extraction

I-shiang Shu, Robert Effinger, Brian Williams, MIT, USA

Discovering Planning Invariants as Anomalies in State Descriptions

Proshanto Mukherji, Lenhart Schubert, University of Rochester, USA

Planning As Mixed-initiative Goal Manipulation

Michael Cox, Chen Zhang, Wright State University, USA

STACS 2005
Symposium on Theoretical Aspects of Computer Science
Stuttgart, Germany, February 24-26, 2005

  1. Nir Ailon and Bernard Chazelle
    Information Theory in Property Testing and Monotonicity Testing in Higher Dimension
  2. Nir Andelman, Yossi Azar and Motti Sorani
    Truthful Approximation Mechanisms for Scheduling Selfish Related Machines
  3. Vikraman Arvind and Thirumalai Chakravarthi Vijayaraghavan
    The Complexity of solving Linear Equations over a Finite Ring
  4. Nikhil Bansal and Kirk Pruhs
    Speed Scaling to Manage Temperature
  5. Surender Baswana, Vishrut Goyal and Sandeep Sen
    All-pairs nearly 2-approximate shortest-paths in O(n^2 polylog n) time
  6. Michael Benedikt and Luc Segoufin
    Regular tree-languages definable in FO
  7. Petra Berenbrink, Tom Friedetzky, Zengjian Hu and Russ Martin
    On Weighted Balls-into-bins Games
  8. Dietmar Berwanger and Giacomo Lenzi
    The variable hierarchy of the mu-calculus is strict
  9. Marcin Bienkowski, Miroslaw Dynia and Miroslaw Korzeniowski
    Improved Algorithms for Dynamic Page Migration
  10. Vittorio Bilò, Michele Flammini and Luca Moscardelli
    On Nash Equilibria in Non-Cooperative All-Optical Networks
  11. Manuel Bodirsky
    The core of a countably categorical structure
  12. Prosenjit Bose, Evangelos Kranakis, Pat Morin and Yihui Tang
    Approximate range mode and range median queries
  13. Ulrik Brandes and Daniel Fleischer
    Centrality Measures Based on Current Flow
  14. Tomas Brazdil, Antonin Kucera and Oldrich Strazovsky
    On the Decidability of Temporal Properties of Probabilistic Pushdown Automata
  15. Harry Buhrman, Ilan Newman, Hein Roehrig and Ronald de Wolf
    Robust Polynomials and Quantum Algorithms
  16. Harry Buhrman, Ilan Newman, Nikolai Vereshchagin and Lance Fortnow
    Increasing Kolmogorov Complexity
  17. Fabio Burderi and Antonio Restivo
    Varieties of Codes and Kraft Inequality
  18. Hubie Chen
    Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms
  19. Jianer Chen, Henning Fernau, Iyad Kanj and Ge Xia
    Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
  20. Josep Diaz, Xavier Perez, Maria Serna and Nicholas Charles Wormald
    Connectivity for wireless agents moving on a cycle or grid
  21. Benjamin Doerr
    Roundings Respecting Hard Constraints
  22. Petros Drineas, Ravi Kannan and Michael Mahoney
    Sampling Sub-problems of Heterogeneous Max-Cut Problems and Approximation Algorithms
  23. Zdeněk Dvořák, Vít Jelínek, Daniel Král', Jan Kynčl and Michael Saks
    Three Optimal Algorithms for Balls of Three Colors
  24. Lars Engebretsen and Jonas Holmerin
    More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP
  25. Kousha Etessami and Mihalis Yannakakis
    Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Non-linear equations
  26. Abraham D. Flaxman and Bartosz Przydatek
    Solving Medium-Density Subset Sum Problems in Expected Polynomial Time
  27. Gianni Franceschini
    Sorting Stably, In-Place, with O(n log n) Comparisons and O(n) Moves
  28. Christian Glaßer
    Polylog-Time Reductions Decrease Dot-Depth
  29. Gregor Gramlich and Georg Schnitger
    Minimizing NFA's and Regular Expressions
  30. Joachim Gudmundsson, Giri Narasimhan and Michiel Smid
    Fast pruning of geometric spanners
  31. Gus Gutoski and John Watrous
    Quantum Interactive Proofs with Competing Provers
  32. Frank Harary, Wolfgang Slany and Oleg Verbitsky
    On the Computational Complexity of the Forcing Chromatic Number
  33. Nicole Immorlica, Mohammad Mahdian and Vahab Mirrokni
    Cycle Cover with Short Cycles
  34. Emmanuel Jeandel
    Topological Automata
  35. Gerard Jennhwa Chang, Antonius J. J. Kloks, Jiping Liu and Sheng-Lung Peng
    The PIGs Full Monty -- A floor show of minimal separators
  36. Detlef Kähler, Ralf Küsters and Thomas Wilke
    Deciding Properties of Contract-Signing Protocols
  37. Michael Kaminski
    A lower bound on the complexity of polynomial multiplication over finite fields
  38. Telikepalli Kavitha and Kurt Mehlhorn
    A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs
  39. Andreas Krebs, Klaus-Jörn Lange and Stephanie Reifferscheid
    Characterizing TC0 in Terms of Infinite Groups
  40. Michal Kunc
    The power of commuting with finite sets of words
  41. Xiang-Yang Li and Zheng Sun
    Cost Sharing and Strategyproof Mechanisms for Set Cover Games
  42. Violetta Lonati and Massimiliano Goldwurm
    Pattern occurrences in multicomponent models
  43. Gregorio Malajovich and Klaus Meer
    Computing Multi-Homogeneous Bézout Numbers is Hard
  44. Wolfgang Merkle, Joseph Miller, Andre Nies, Jan Reimann and Frank Stephan
    Kolmogorov-Loveland Randomness and Stochasticity
  45. Graham P Oliver and Richard M Thomas
    Automatic presentations for finitely generated groups
  46. Victor Poupet
    Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoods
  47. Sasanka Roy, Sandip Das and Subhas C. Nandy
    Shortest Monotone Descent Path Problem in Polyhedral Terrain
  48. Markus Schmidt
    Packet Buffering - Randomization Beats Deterministic Algorithms
  49. Amnon Ta-Shma and Eran Rom
    Improving the alphabet-size in high noise, almost optimal rate list decodable codes.
  50. Seiichiro Tani, Hirotada Kobayashi and Keiji Matsumoto
    Deterministic Leader Election via Distributed Quantum Computing
  51. Lidia Tendera
    Counting in the two variable guarded logic with transitivity
  52. Guillaume Theyssier
    How Common Can Be Universality for Cellular Automata
  53. Volker Weber and Thomas Schwentick
    Dynamic Complexity Theory Revisited
  54. Carsten Witt
    Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics

LPAR 2004
Logic for Programming Artificial Intelligence and Reasoning
Montevideo, Uruguay, March 14-18, 2005

Marco Benedetti. Evaluating QBFs via Symbolic Skolemization
Ullrich Hustadt, Boris Motik and Ulrike Sattler. A Decomposition Rule for Decision Procedures by Resolution-based Calculi
Carsten Schuermann and Mark-Oliver Stehr. An Executable Formalization of the HOL/Nuprl Connection in the Metalogical Framework Twelf
Nathan Whitehead and Martín Abadi. BCiC: A System for Code Authentication and Verification
Mark Bickford, Robert Constable, Joseph Halpern and Sabina Petride. Knowledge-Based Synthesis of Distributed Systems Using Event Structures
Christoph Walther and Stephan Schweitzer. Automated Termination Analysis for Incompletely Defined Programs
Christopher Hardin. How the Location of * Influences Complexity in Kleene Algebra with Tests
Thomas Linke and Vladimir Sarsakov. Suitable Graphs for Answer Set Programming
Pascal Fontaine, Silvio Ranise and Calogero G. Zarba. Combining Lists with Non-Stably Infinite Theories
Thomas Eiter, Giovambattista Ianni, Roman Schindlauer and Hans Tompits. Nonmonotonic Description Logic Programs: Implementation & Experiments
Lennart Beringer, Martin Hofmann, Alberto Momigliano and Olha Shkaravska. Automatic Certification of Heap Consumption
George Metcalfe, Agata Ciabattoni and Christian Fermueller. Uniform Rules and Dialogue Games for Fuzzy Logics
Jerzy Marcinkowski, Jan Otop and Grzegorz Stelmaszek. On a Semantic Subsumption Test
Miyuki Koshimura, Mayumi Umeda and Ryuzo Hasegawa. Abstract Model Generation for Preprocessing Clause Sets
Albert Oliveras, Robert Nieuwenhuis and Cesare Tinelli. Abstract DPLL and Abstract DPLL Modulo Theories
Vilhelm Dahllof. Applications of General Exact Satisfiability in Propositional Logic Modelling
Roberto Di Cosmo and Thomas Dufour. The theory of <N,0,1,+,.,^> is decidable, but not finitely axiomatisable.
Dietmar Berwanger and Erich Graedel. Entanglement -- A Measure for the Complexity of Directed Graphs With Applications to Logic and Games
Kevin Donnelly, Tyler Gibson, Neel Krishnaswami, Stephen Magill and Sungwoo Park. The Inverse Method for the Logic of Bunched Implications
Jeff Polakow and Pablo Lopez. Implementing Efficient Resource Management for Linear Logic Programming
Daniel Gorín and Carlos Areces. Ordered resolution with selection for H(@)
Paul Hankes Drielsma, Sebastian Mödersheim and Luca Viganò. A Formalization of Off-Line Guessing for Security Protocol Analysis
Davy Van Nieuwenborgh, Stijn Heymans and Dirk Vermeir. Weighted Answer Sets and Applications in Intelligence Analysis
Norbert Schirmer. A Verification Environment for Sequential Imperative Programs in Isabelle/HOL
Bejamin Aminof, Thomas Ball and Orna Kupferman. Reasoning about Systems with Transition Fairness
Helmut Seidl and Kumar Neeraj Verma. Flat and One-Variable Clauses: Complexity of Verifying Cryptographic Protocols with Single Blind Copying
Flavio L. C. de Moura, Fairouz Kamareddine and Mauricio Ayala Rincon. Second-Order Matching via Explicit Substitutions
Jamshid Bagherzadeh and S. Arun-Kumar . Layered Clausal Resolution in the Multi-Modal Logic of Beliefs and Goals
Stefan Hetzl, Matthias Baaz, Alexander Leitsch, Clemens Richter and Hendrik Spohr. Cut-Elimination: Experiments with CERES
Lucas Bordeaux, Marco Cadoli and Toni Mancini. Exploiting Fixable, Substitutable and Determined Values in Constraint Satisfaction Problems
German Puebla, Manuel Hermenegildo and Elvira Albert. Abstraction-Carrying Code
Christoph Benzmueller, Volker Sorge, Mateja Jamnik and Manfred Kerber. Can a Higher-Order and a First-Order Theorem Prover Cooperate?
Gustav Nordh. A Trichotomy in the Complexity of Propositional Circumscription