This volume contains the proceedings of the 6th Symposium on Abstraction, Reformulation and Approximation (SARA 2005). The symposium was held at Airth Castle, Scotland, UK, from July 26th to 29th, 2005, just prior to the IJCAI 2005 conference in Edinburgh. Previous SARA symposia took place at JacksonHole in Wyoming, USA (1994),Ville d'Estrel in Qubec, Canada (1995), Asilomar in California, USA (1998), Horseshoe Bay, Texas, USA (2000), and Kananaskis, Alberta, Canada (2002). This was then the ?rst time that the s- posium was held in Europe. Continuing the tradition started with SARA 2000, the proceedings have been published in the LNAI series of Springer. Abstractions, reformulations and approximations (AR&A) have found app- cationsin avarietyofdisciplines andproblems,including constraintsatisfaction, design, diagnosis, machine learning, planning, qualitative reasoning, scheduling, resource allocation and theorem proving, but are also deeply rooted in philo- phy and cognitive science. The papers in this volume capture a cross-section of the various facets of the ?eld and of its applications. One of the primary uses of AR&A is oriented to overcome computational intractability. AR&A techniques, however, have also proved useful for knowledge acquisition, explanation and other applications, as papers in this volume also illustrate.

Table of Contents:
Full Papers.- Verifying the Incorrectness of Programs and Automata.- Generating Admissible Heuristics by Abstraction for Search in Stochastic Domains.- Synthesizing Plans for Multiple Domains.- Abstract Policy Evaluation for Reactive Agents.- Implementing an Abstraction Framework for Soft Constraints.- Transforming and Refining Abstract Constraint Specifications.- Learning Regular Expressions from Noisy Sequences.- From Factorial and Hierarchical HMM to Bayesian Network: A Representation Change Algorithm.- Hierarchical Heuristic Search Revisited.- Multinomial Event Model Based Abstraction for Sequence and Text Classification.- Petri Net Reachability Checking Is Polynomial with Optimal Abstraction Hierarchies.- Detecting and Breaking Symmetries by Reasoning on Problem Specifications.- Approximate Model-Based Diagnosis Using Preference-Based Compilation.- Function Approximation via Tile Coding: Automating Parameter Choice.- Creating Better Abstract Operators.- A Specialised Binary Constraint for the Stable Marriage Problem.- Compositional Derivation of Symmetries for Constraint Satisfaction.- Extended Abstracts.- Solving the 24 Puzzle with Instance Dependent Pattern Databases.- Combining Feature Selection and Feature Construction to Improve Concept Learning for High Dimensional Data.- A Qualitative Spatio-temporal Abstraction of a Disaster Space.- The Cruncher: Automatic Concept Formation Using Minimum Description Length.- Experiments with Multiple Abstraction Heuristics in Symbolic Verification.- Probabilistic Abstraction of Uncertain Temporal Data for Multiple Subjects.- Learning Classifiers Using Hierarchically Structured Class Taxonomies.- Feature-Discovering Approximate Value Iteration Methods.- Invited Talks.- Designing Views to Efficiently Answer Real SQL Queries.-The Multi-depot Periodic Vehicle Routing Problem.- Abstract Representation in Painting and Computing.- Research Summaries.- Categorizing Gene Expression Correlations with Bioclinical Data: An Abstraction Based Approach.- Learning Abstract Scheduling Models.- Knowledge Acquisition on Manipulation of Flow and Water Quality Models.- Abstraction and Multiple Abstraction in the Symbolic Modeling of the Environment of Mobile Robots.- Sequential Decision Making Under Uncertainty.- Automatic State Abstraction for Pathfinding in Real-Time Video Games.- Model-Based Search.- Learning Skills in Reinforcement Learning Using Relative Novelty.