About the Completeness of Depth-First Proof-Number Search
Depth-first proof-number (df-pn) search is a powerful member of the family of algorithms based on proof and disproof numbers. While df-pn has succeeded in practice, its theoretical properties remain poorly understood. This paper resolves the question of completeness of df-pn: its ability to solve any finite boolean-valued game tree search problem in principle, given unlimited amounts of time and memory. The main results are that df-pn is complete on finite directed acyclic graphs (DAG) but incomplete on finite directed cyclic graphs (DCG).

title: Automating Layouts of Sewers in Subdivisions
abstract: An important part of the creation of a housing subdivision is the design and layout of sewers underneath the road. This is a challenging cost optimization problem in a continuous threedimensional space. In this paper, heuristic-search-based techniques are proposed for tackling this problem. The result is new algorithms that can quickly find near optimal solutions that offer important reductions in the cost of design and construction.

title: Action Elimination and Plan Neighborhood Graph Search: Two Algorithms for Plan Improvement
abstract: Compared to optimal planners, satisficing planners can solve much harder problems but may produce overly costly and long plans. Plan quality for satisficing planners has become increasingly important. The most recent planning competition IPC-2008 used the cost of the best known plan divided by the cost of the generated plan as an evaluation metric. This paper proposes and evaluates two simple but effective methods for plan improvement: Action Elimination improves an existing plan by repeatedly removing sets of irrelevant actions. Plan Neighborhood Graph Search finds a new, shorter plan by creating a plan neighborhood graph PNG(π) of a given plan π, and then extracts a shortest path from PNG(π). Both methods are implemented in the ARAS postprocessor and are empirically shown to improve the result of several planners, including the top four planners from IPC-2008, under competition conditions.

title: Monte-Carlo Exploration for Deterministic Planning
abstract: Search methods based on Monte-Carlo simulation have recently led to breakthrough performance improvements in difficult game-playing domains such as Go and General Game Playing. Monte-Carlo Random Walk (MRW) planning applies Monte-Carlo ideas to deterministic classical planning. In the forward chaining planner ARVAND, Monte-Carlo random walks are used to explore the local neighborhood of a search state for action selection. In contrast to the stochastic local search approach used in the recent planner Identidem, random walks yield a larger and unbiased sample of the search neighborhood, and require state evaluations only at the endpoints of each walk. On IPC-4 competition problems, the performance of ARVAND is competitive with state of the art systems.

title: Lambda Depth-First Proof Number Search and Its Application to Go
abstract: Thomsen's λ search and Nagai's depth-first proof-number (DFPN) search are two powerful but very different AND/OR tree search algorithms. Lambda Depth-First Proof Number search (LDFPN) is a novel algorithm that combines ideas from both algorithms. λ search can dramatically reduce a search space by finding different levels of threat sequences. DFPN employs the notion of proof and disproof numbers to expand nodes expected to be easiest to prove or disprove. The method was shown to be effective for many games. Integrating λ order with proof and disproof numbers enables LDFPN to select moves more effectively, while preserving the efficiency of DFPN. LDFPN has been implemented for capturing problems in Go and is shown to be more efficient than DFPN and more robust than an algorithm based on classical λ search.

title: A General Solution to the Graph History Interaction Problem
abstract: Since the state space of most games is a directed graph, many game-playing systems detect repeated positions with a transposition table. This approach can reduce search effort by a large margin. However, it suffers from the so-called Graph History Interaction (GHI) problem, which causes errors in games containing repeated positions. This paper presents a practical solution to the GHI problem that combines and extends previous techniques. Because our scheme is general, it is applicable to different game tree search algorithms and to different domains. As demonstrated with the two algorithms αβ and df-pn in the two games checkers and Go, our scheme incurs only a very small overhead, while guaranteeing the correctness of solutions.

title: A Comparison of BPML and BPEL4WS
abstract: Web services composition receives an increasing attention as a concept to build business processes from. This paper addresses the heterogeneity of business process modeling specifications in the area of web services. A new concept called metadata relationships (MR) is introduced to describe the semantic relationship between concepts from two different XML Schemas. This approach is applied for the comparison of concepts from BPML and BPEL4WS, the two major proposals to become a standard in the area of Web Service composition. Metadata relationships are aggregated to discuss the interrelation of these two specifications. The results show that there is a large overlap between the two specifications. Therefore, an integration of them into only one specification seems feasible and desirable. 1. Comparing Business Process Modeling Methods Business Process Modeling (BPM) addresses the domain of logical dependencies of consecutive activities. In this area many different modeling methods have been developed to semantically depict these dependencies in a predefined syntax. The advantages of such formal methods are to be found in the ease of communication, the use of formal analyses, and the implementation in information systems. Business process modeling specifications in the context of Web Services provide functionality like transactions, process execution, choreography of message exchange, or exception handling. These aspects go beyond stateless communication provided by a core Web Services’ architecture built on the Simple Open Acces Protocol (SOAP) [Gu03a], [Gu03b], Web Service Description Language (WSDL) [Ch03], [Gu03c], [Mo03], and Universal Description, Discovery & Integration (UDDI) [Be02]. Such an architecture involves three parties: a service provider, a service broker, and a service requester [TP02]. WSDL is used by a service provider to describe a service which then can be published in an UDDI registry of a service broker. A service requester retrieves the WSDL document via UDDI registry and uses it for binding. Messages are exchanged via SOAP. All these standards are based on the eXtensible Markup Language (XML) [Br00] allowing an easy transportation on top of common Internet protocols like HTTP. Various specifications have been proposed for BPM of Web Services . The Business Process Execution Language fro Web Services ( BPEL4WS) [An03], the Business Process Modeling Language (BPML)  are proposals dedicated to the composition of various Web Services to become a business process. The ebXML Business Process Specification Schema (BPSS) [UN01], the Web Service Choreography Interface (WSCI) [Ar02b], and the Web Service Conversation Language (WSCL) [Ba02] deal with choreography or conversation, that is the allowed sequence of message exchanges from an external point of view. All of these languages offer an XML-based syntax and they are specially developed to address requirements in the area of WS. Yet, the the expressive power of these specifications are too little investigated with respect to a common benchmark. Van der Aalst et al. use so called workflow and communication patterns and express them with concepts of BPML [Aa02] and BPEL4WS [Wo02]. But in order to better understand these two proposals , transformations are needed that map constructs of their meta model to other better known concepts. The DARPA Agent Markup Language – Services (DAML-S) [DA03] seems to be a natural candicate by developing a extensive ontology on Web Services. This paper complements the efforts of DAML-S by comparing the expressive power of BPML and BPEL4WS activities . Since the merger of WSFL and XLANG to become BPEL4WS they are the two major candidates to gain the status of a standard for Web Service composition. Both of these vocabularies are expressed in XML, permitting the comparison of their metadata, which are elements and attributes defined by their respective XML Schemas [Be01], [BM01]. In section 2 a new approach is introduced called metadata relationships (MR) and schema relationships (SR). This allows for a semi-formal, but in depth analysis of the semantic interrelation of metadata elements from two different schemas. Section 3 discusses metadata relations (MR) between activities supported in BPML and BPEL4WS. The final section outlines future research. 2. Metadata Relationships and Schema Relationships 2.1. Metadata Relationships on the Micro Level The integration of data from different metadata schemas has been discussed since the advent of database systems. Classifications of potential conflicts have been proposed by [CW93] and [SPD92] to name but a few. Generally, a micro and a macro perspective can be distinguished. The micro perspective refers to conflicts due to different representations of concepts in two schemas. The macro perspective allows statements about the relation of entire schemas. We introduce Metadata Relationships (MR) as a concept on the micro level. MR refer to how concepts of a schema A are related to concepts from another schema B. Such concepts are identified by metadata elements of the respective XML Schema or DTD. Accordingly, we define a Metadata-Set MA of a schema A as a set of all elements and attributes that are defined in the XML Schema or DTD of A. A MR(a,b) is formally defined for a ⊆ MA and b ⊆ MB. MR may be of eight different types: the first three are called symmetric MR, the next three are called asymmetric MR, and the last two are called incomplete MR. The symmetric MR are related to cardinalities known from Entity-Relationship Diagrams [Ch76]. But in contrast to ERD cardinalities that refer to relations between entities in one single schema, MR refer to relations between concepts from two different schemas. Symmetric MR describe the situation when a concept a ⊆ MA from one schema A can always be mapped to a concept b ⊆ MB from the other schema B, and when this concept b can also always be mapped to the same concept a of the first schema. From this follows that symmetric MR allow bidirectional transformations. Asymmetric MR permit only one way transformations without loss of information. Incomplete MR refer to concepts that partially intersect or that are not included in the other schema at all. 1. Symmetric MR(1:1) 1:1-MR refer to concepts from different schemas that are semantically equivalent. This MR addresses naming and domain conflicts as describes by Ceri et al. [CW93]. An example would be “Auto” from a German schema G and “Car” from an English schema E. We then write MR(G.Auto, ) = MR(1:1). 2. Symmetric MR(1:N) 1:N-MR address the problem of different levels of abstraction of two concepts. Things may be modeled in terms of data of metadata leading to meta-data conflicts [CW93]. Note, that a MR can only be symmetric when concepts b1, b2,...,bn of the second schema B describe a partition over the concept a of the first schema A. If there is a residue from the intersection of both sets of concepts, no round trip is possible without loss of information. For example, take two different schemas called A and B. A only knows the general concept of “parent”, B distinguished between “mother” and “father”. Then, a “parent” of A can always be mapped to either “mother” or “father” from schema B, and “mother” and “father” can always be mapped to “parent”. The concepts address the same set of instances without residue. A round-trip is possible without loss of information. The actual decision whether a parent is a mother or a father cannot be taken on the level of metadata, it depends on additional information from the data level. We write MR(A.parent, {B.father, B.mother}) = MR(1:N). 3. Symmetric MR(N:M) The N:M-MR is similar to the 1:N-MR, but now both schemas describe a partition of one and the same concept, that is not explicitly modeled in both schemas. An example may be a schema P1 that differentiates between male and female, and another schema P2 distinguishing between minors and adults. Both describe a partition of people. Using additional information from the data level, the metadata concepts can be mapped. We write MR ({P1.male, P1.female}, {P2.minor, P2.adults}) = MR(N:M). 4. Asymmetric MR(1:X) The asymmetric 1:X-MR describes a concept that is a subset of the second concept. On the one hand, this allows for a transformation from the first concept to the second concept without loss of information. On the other hand, a transformation from the second concept to the first one leads to a loss of information, because not all instances can be expressed in terms of the first schema. Take a schema A that explicitly models the concept “bus”, and a second schema B with a concept “car”. All instances of bus are also instances of the concept car. But not all instances from car are also busses, leading to a loss of information when there is a transformation from B.car to A.bus. We write MR(A.bus, B.car) = MR(1:X). 5. Asymmetric MR(N:X) The N:X-MR is similar to the 1:X-MR. Imagine schema A also containing a concept called “truck”. There is a 1:X-MR between A.bus and B.car, and also between A.truck and B.car. The N:X-MR is an abbreviation for this which allows to capture all to B.car related concepts of A in one expression. We write MR({A.bus, A.truck}, B.car) = MR(N:X). 6. Asymmetric MR(1:S) The 1:S-MR refers to a subcomponent-relation or a definition. Concepts of the first schema can be simulated in terms of a block of concepts from the other schema. For example take a schema A.route and a schema B with the concept street. The concept route captures the semantics of a certain sequence of streets to follow in order to get from one place to another. This allows A.route to be simulated by a set of B.streets, but streets cannot be expressed in terms of schema A’s route. We write MR(A.route, B.street) = MR(1:S) 7. Incomplete MR(X:Y) The X:Y-MR describes intersecting concepts with none of both being a subset of the other. Fo

title: PAN - The Prolog Analyzer

title: TabVer: A Case Study in Table Verbalization
abstract: The purpose of this paper is to give a brief overview of TabVer, a front-end component that verbalizes large tables generated by a commercial expert system.