Game-SAT: A Preliminary Report
Game-SAT is a 2-player version of SAT where two players (MAX and MIN) play on a SAT instance by alternatively selecting a variable and assigning it a value true or false. MAX tries to make the formula true, while MIN tries to make it false. The Game-SAT problem is to determine the winner of a SAT instance under the rules above, assuming the perfect play by both players. The Game-SAT problem, originally derived from an application in adversarial planning, is PSPACE-complete. The problem is similar to QBF, but differs by the property of free variable selection, compared to QBF with its fixed variable ordering. We have developed a Game-SAT solver, Gasaso, that uses a combination of standard game tree search techniques, search methods that are well known in the SAT community, and specialized pruning techniques. We show empirically how the solver performs in this new domain, and give evidence for the existence of phase transitions in this problem.

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: 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: An Improved Safety Solver for Computer Go
abstract: Most Go-playing programs use a combination of search and heuristics based on an influence function to determine whether territories are safe. However, to assure the correct evaluation of Go positions, the safety of stones and territories must be proved by an exact method. 
 
The first exact algorithm, due to Benson , determines the unconditional safety of stones and completely surrounded territories.  develops static rules for detecting safety by alternating play, and introduces search-based methods. 
 
This paper describes new, stronger search-based techniques including region-merging and a new method for efficiently solving weakly dependent regions. In a typical final position, more than half the points on the board can be proved safe by our current solver. This almost doubles the number of proven points compared to the 26.4% reported in .

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: Depth-First Discovery Algorithm for incremental topological sorting of directed acyclic graphs
abstract: We study the problem of incrementally maintaining a topological sorting in a large DAG. The Discovery Algorithm of Alpern et al.  computes a cover K f nodes such that a solution to the modified problem can be found by changing node priorities within K only. It achieves a runtime complexity that is polynomially bounded in terms of the minimal cover size k. The temporary space complexity of DA grows quickly with increasing number of added edges and cover size. We in the Depth-First Discovery Algorithm (DFDA), which uses depth-first search to reduce the temporary space of D O(|A| × ‖K‖) to O(|A| + ‖K‖), where|A| is the number of edges to add and ‖K‖ is theextended size of the cover. DFDA is simpler than DA and performs better in our empirical tests.  2003 Elsevier B.V. All rights reserved.

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.

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].