Conditional combinatorial games and their application to analyzing capturing races in Go
Conditional combinatorial games (CCG) are a new tool developed for describing loosely coupled games. The definition of CCG is based on the one for classical independent combinatorial games. However, play in a CCG depends on its global context: certain moves are legal only if a nonlocal context condition is currently true. Compared with independent combinatorial games, CCG only allow some weaker forms of pruning. The first part of this paper starts to develop a theory of CCG and gives some examples.In the second part, CCG are shown to be useful for studying capturing races called semeai in the game of Go. We introduce a general framework for analyzing semeai, which is based on CCG and on an extension called liberty count games. We show how this framework encompasses and extends our earlier work on solving semeai [M. Muller, Race to capture: Analyzing semeai in Go,  1999, p. 61].

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: 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: 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: 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: 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: Weblogs, Legitimacy and Organizations
abstract: The last decades have seen a movement of production to less economically developed countries. These countries often don’t meet Western social and environmental standards. Non-governmental organizations (NGOs) have challenged poor conditions such as child labor, discrimination or environmental pollution caused by suppliers. Purchasers are criticized in the public realm, which leads to damage to their reputation [Hansen and Schrader 2005; Gilbert 2003]. Nike, Dole Foods and GM have experienced such campaigns [Lawrence 2002]. Focal companies with direct contact to the end customer and big labels are most vulnerable to this strategy. A loss of reputation may weaken their ability to compete and result in decreasing sales volume [Hansen and Schrader 2005].

title: Automated Modular Termination Proofs for Real Prolog Programs
abstract: We present a methodology for checking the termination of Prolog programs that can be automated and is scalable. Furthermore, the proposed method can be used to locate errors. It has been successfully implemented as part of a tool that uses static analysis based on formal methods in order to validate Prolog programs. This tool is aimed at supporting the design and maintenance of Prolog programs.