Acquiring correct action theories from informal specifications remains a central challenge in KR. Large Language Models can generate plausible domain models from natural language, but the resulting theories frequently contain missing preconditions, incorrect effects, or superfluous actions. Existing refinement approaches either require human experts to correct these errors or assume that the input specification is itself correct. We present a fully automated framework that iteratively refines LLM-generated action theories using formal explanations grounded in SAT-based verification. Each candidate theory is encoded as a bounded SAT problem and tested against solvable tasks, which must admit a valid plan, and unsolvable tasks, which must be correctly rejected. When a test fails, we extract a formal explanation that pinpoints the specific theory constraints responsible for the failure, and feed this explanation back to the LLM to guide its next revision. Our initial evaluation across six planning domains shows that our framework can converge to correct theories.

The Bin Packing Problem is one of the most important problems in discrete optimization, as it captures the requirements of many real-world problems. Because of its importance, it has been approached with the main theoretical and practical tools. Resolution approaches based on Linear Programming are the most effective, while Constraint Programming proves valuable when the Bin Packing Problem is a component of a larger problem. This work focuses on the Bin Packing constraint and explores how GPUs can be used to enhance its propagation algorithm. Two approaches are motivated and discussed, one based on knapsack reasoning and one using alternative lower bounds. The implementations are evaluated in comparison with state-of-the-art approaches on different benchmarks from the literature. The results indicate that the GPU-accelerated lower bounds offers a desirable alternative to tackle large instances.

This innovative practice WIP paper describes how undergraduate students developed their curriculum development skills while designing an after-school program for learning computational thinking through writing. DEPICT (Discovering Computational Thinking through Creative Writing) is a pioneering project aimed at integrating computational thinking (CT) principles into high school (HS) creative writing (CW) classes. Developed by computer science (CS) undergraduate students, DEPICT for Out for School Time (DEPICT4OST) introduces a set of 16 innovative lessons designed to foster critical thinking, problem-solving, and algorithmic reasoning through the medium of CW. This WIP presents an exploration of the undergraduate experience in apprenticeship in the K12 outreach instructional space, crafting the DEPICT curriculum and the transformative journey of teaching others through the creation of engaging hands-on activities. Data was collected through pre- and post program surveys, classroom observations, and student work samples to assess the impact of the DEPICT program. The analysis involved comparing quantitative survey results, coding qualitative data from observations and students reflections, and evaluating changes in student work to determine the effectiveness of the program in achieving its educational goals. Drawing upon their expertise in CS and passion for creative expression, the undergraduate team embarked on the task of bridging the seemingly disparate domains of CT and CW. Through collaborative brainstorming sessions, iterative design processes, and pedagogical research, they developed a diverse range of lesson plans that seamlessly integrate computational concepts into writing prompts, narrative structures, and story-telling techniques. The practices of DEPICT4OST build upon a departmental emphasis on student ownership of outreach activity, which will be described in the paper. The paper explores the challenges of adapting complex computational concepts for HS students and aligning activities with educational standards. It also highlights the creative solutions the undergraduate team developed to make these abstract principles accessible and engaging through interactive writing exercises, group discussions, and multimedia presentations. Furthermore, the paper explores the pedagogical insights gained through the hands-on experience of teaching the DEPICT curriculum to HS students. The undergraduates reflect on their role as facilitators of learning, the impact of active learning techniques on student engagement, and the evolution of their teaching practices. By sharing anecdotes, student feedback, and reflections, the paper offers valuable insights into the effectiveness of infusing CT into CW education. In conclusion, DEPICT represents a pioneering initiative that harnesses the interactions between CT and creative expression to enrich HS education. The paper not only documents the development of the DEPICT curriculum but also underscores the transformative potential of collaborative, interdisciplinary approaches to education. Through the exploration of the under-graduate experience, it offers a roadmap for future endeavors seeking to innovate in the realm of STEAM education.

We attempted to address the challenge of effectively conveying the innovative literary device known as the Rashomon effect (tRe), using a digital tool. We opted for Augmented Reality (AR) in combination with MERGE cubes for this purpose. These cubes served as a practical medium for illustrating the complexities of tRe, a narrative technique renowned for its ability to offer multiple perspectives on a single event or storyline. This narrative device is known for its ability to create narrative uncertainty, withholding a clear and absolute truth, and instead exposing the readers to an assortment of interpretations. The Rashomon Augmented Reality Cube (RARc) was designed with two main goals in mind. Firstly, it was created to provide a vivid visual representation of the Rashomon effect. This not only makes storytelling engaging but also serves as a stepping stone for students to explore a variety of interpretations. Secondly, it was conceived as an educational tool for introducing students to key CT principles, such as abstraction, solution design, and computational innovations. By instilling these principles, students acquire problem-solving skills that are increasingly essential in our technology-driven world. This AR tool, known as the RARc, serves as a hands-on digital activity crafted for creative writers, with a particular focus on engaging female participants. It encourages them to unleash their creativity and explore the nuances of storytelling within an immersive and interactive learning experience. In this paper, we share development and implementation strategies that were utilized throughout the design of the RARc. The Rashomon Augmented Reality Cube (RARc) was designed with two main goals in mind. Firstly, it was created to provide a vivid visual representation of the Rashomon effect. This not only makes storytelling engaging but also serves as a stepping stone for students to explore a variety of interpretations. Secondly, it was conceived as an educational tool for introducing students to key CT principles, such as abstraction, solution design, and computational innovations. By instilling these principles, students acquire problem-solving skills that are increasingly essential in our technology-driven world. This AR tool, known as the RARc, serves as a hands-on digital activity crafted for creative writers, with a particular focus on engaging female participants. It encourages them to unleash their creativity and explore the nuances of storytelling within an immersive and interactive learning experience. In this paper, we share development and implementation strategies that were utilized throughout the design of the RARc.

In our modern society, technology has profoundly reshaped various aspects of our lives, influencing the way we work, communicate, and interact. This raises a fundamental question: Is the current K-12 education system adequately preparing students for success in this technology-driven era, where innovation and problem-solving skills are essential? A recent study investigated this inquiry. The goal was to integrate Computational Thinking (CT) into the domains of Creative Writing and Creative Media and measure its impacts. This poster describes the design and refinement of summer camp experiences in which predominantly Hispanic female students participated in hands-on CT-based learning to create their own creative stories and films. Educational outcomes were evident through increased student engagement, enhanced collaboration, and improved problem-solving skills, underscoring the intervention's advantages. Furthermore, the researchers gained transforming insights, recognizing the versatility of CT across domains. Camp participants experienced a shift in perspective, with a greater interest in vocations and domains connected to computing. We share lessons learned from these summer camps in the hopes that they will inform other researchers and practitioners who are interested in designing and deploying similar experiences. In summary, the study outlines a trajectory where students and educators skillfully navigate the complexities of contemporary paradigms

Abstract The AllDifferent constraint is a fundamental tool in Constraint Programming. It naturally arises in many problems, from puzzles to scheduling and routing applications. Such popularity has prompted an extensive literature on filtering and propagation for this constraint. This paper investigates the use of General Processing Units (GPUs) to accelerate filtering and propagation. In particular, the paper presents an efficient parallelization of the AllDifferent constraint on GPU, along with an analysis of different design and implementation choices and evaluation of the performance of the resulting system on several benchmarks.

This issue of TPLP contains selected papers of the 39 th

status: Published

Abstract Answer Set Planningrefers to the use ofAnswer Set Programming (ASP)to computeplans, that is, solutions to planning problems, that transform a given state of the world to another state. The development of efficient and scalable answer set solvers has provided a significant boost to the development of ASP-based planning systems. This paper surveys the progress made during the last two and a half decades in the area of answer set planning, from its foundations to its use in challenging planning domains. The survey explores the advantages and disadvantages of answer set planning. It also discusses typical applications of answer set planning and presents a set of challenges for future research.

The New Mexico teaching workforce does not mirror the demographics of the student population. 60% of NM teachers are white, 34% are Hispanic, and only 3% are Native American, while 61% of NM students are Hispanic, 25% are white, and 11% are Native American, almost guaranteeing that students will not be taught by someone that shares their background and experiences. A potential remedy of this mismatch is for teachers to embrace culturally responsive pedagogy. The goal of this BoF session is to promote a collaborative conversation about mechanisms to expand the under- standing of culturally responsive pedagogy among K-12 computer science teachers and other relevant stakeholders.

Abstract Multi-core and highly connected architectures have become ubiquitous, and this has brought renewed interest in language-based approaches to the exploitation of parallelism. Since its inception, logic programming has been recognized as a programming paradigm with great potential for automated exploitation of parallelism. The comprehensive survey of the first twenty years of research in parallel logic programming, published in 2001, has served since as a fundamental reference to researchers and developers. The contents are quite valid today, but at the same time the field has continued evolving at a fast pace in the years that have followed. Many of these achievements and ongoing research have been driven by the rapid pace of technological innovation, that has led to advances such as very large clusters, the wide diffusion of multi-core processors, the game-changing role of general-purpose graphic processing units, and the ubiquitous adoption of cloud computing. This has been paralleled by significant advances within logic programming, such as tabling, more powerful static analysis and verification, the rapid growth of Answer Set Programming, and in general, more mature implementations and systems. This survey provides a review of the research in parallel logic programming covering the period since 2001, thus providing a natural continuation of the previous survey. In order to keep the survey self-contained, it restricts its attention to parallelization of the major logic programming languages (Prolog, Datalog, Answer Set Programming) and with an emphasis on automated parallelization and preservation of the sequential observable semantics of such languages. The goal of the survey is to serve not only as a reference for researchers and developers of logic programming systems but also as engaging reading for anyone interested in logic and as a useful source for researchers in parallel systems outside logic programming.

The first issue of the journal Theory and Practice of Logic Programming, or TPLP, was published in January 2001.This issue, the last one in the present volume, and the following issue, the first one in the next volume, comprise a collection of papers commemorating and celebrating the twentieth anniversary of the journal.This celebratory collection comes with about one year delay due to the COVID-19 pandemic (but also, if we were to be entirely honest, because of a common human tendency to put things off).Whatever the true reason for the delay, the collection is finally here.We hope and expect it will prove to be a demonstration of the vitality of logic programming, and of a broad range of research directions it spawned in the past and continues to generate today.Logic programming appeared as a scientific subarea of computer science in the early 1970s as a result of the happy confluence of research on automated theorem proving in first-order logic and the original implementation of the Prolog programming language.The presence of these two original sources of inspiration has been distinctly felt over the years.On the one hand, logic programming attracted theoreticians pursuing deeper and highly nuanced understanding of the semantics of logic programs; on the other hand, it drew in researchers whose goal was to advance the repertoire of logic programming tools by refining, perfecting, and expanding Prolog, proposing and implementing new computational paradigms for logic programming, and developing methods to build and analyze logic programs.Moreover, and it also goes back to its very origins, logic programming attracted researchers interested in applications such as natural language processing, database querying, constraint solving, planning, learning, and knowledge representation, to name but a few.

The paper proposes a framework for capturing how an agent’s beliefs evolve over time in response to observations and for answering the question of whether statements made by a third party can be believed. The basic components of the framework are a formalism for reasoning about actions, changes, and observations and a formalism for default reasoning. The paper describes a concrete implementation that leverages answer set programming for determining the evolution of an agent's ``belief state'', based on observations, knowledge about the effects of actions, and a theory about how these influence an agent's beliefs. The beliefs are then used to assess whether statements made by a third party can be accepted as truthful. The paper investigates an application of the proposed framework in the detection of man-in-the-middle attacks targeting computers and cyber-physical systems. Finally, we briefly discuss related work and possible extensions.

Access and reuse of authoritative phylogenetic knowledge have been a longstanding challenges in the evolutionary biology community — leading to a number of research efforts (e.g. focused on interoperation, standardization of formats, and development of minimum reporting requirements). The Phylotastic project was launched to provide an answer to such challenges — as an architectural concept collaboratively designed by evolutionary biologists and computer scientists. This paper describes the first comprehensive implementation of the Phylotastic architecture, based on an open platform for Web services composition. The implementation provides a portal, which composes Web services along a fixed collection of workflows, as well as an interface to allow users to develop novel workflows. The Web services composition is guided by automated planning algorithms and built on a Web services registry and an execution monitoring engine. The platform provides resilience through seamless automated recovery from failed services.

Abstract Designing agents that reason and act upon the world has always been one of the main objectives of the Artificial Intelligence community. While for planning in “simple” domains the agents can solely rely on facts about the world, in several contexts,e.g., economy, security, justice and politics, the mere knowledge of the world could be insufficient to reach a desired goal. In these scenarios,epistemicreasoning,i.e., reasoning about agents’ beliefs about themselves and about other agents’ beliefs, is essential to design winning strategies. This paper addresses the problem of reasoning in multi-agent epistemic settings exploiting declarative programming techniques. In particular, the paper presents an actual implementation of a multi-shotAnswer Set Programming-based planner that can reason in multi-agent epistemic settings, called PLATO (ePistemic muLti-agentAnswer seTprogramming sOlver). The ASP paradigm enables a concise and elegant design of the planner, w.r.t. other imperative implementations, facilitating the development of formal verification of correctness. The paper shows how the planner, exploiting an ad-hoc epistemic state representation and the efficiency of ASP solvers, has competitive performance results on benchmarks collected from the literature.

This paper presents an extension of the Multi-Context Systems (MCS) framework to allow the encoding of preferences at the level of the contexts. The work is motivated by the observation that a naive use of preference logics at a context level in an MCS can lead to undesirable outcomes, such as inco nsistency of the MCS. To address this issue, the paper introduces the notion of ranked logics, suitable for use with multiple sources of preferences, and employs them in the definition of weakly and strongly-preferred equilibria in a Multi-Context Systems with Preferences (MCSP) framework. The usefulness of MCSP is demonstrated in two applications: modeling distributed configuration problems and finding explanations for distributed abductive diagnosis problems.

The field of multi-agent system (MAS) is an active area of research within artificial intelligence, with an increasingly important impact in industrial and other real-world applications. In a MAS, autonomous agents interact to pursue personal interests and/or to achieve common objectives. Distributed Constraint Optimization Problems (DCOPs) have emerged as a prominent agent model to govern the agents' autonomous behavior, where both algorithms and communication models are driven by the structure of the specific problem. During the last decade, several extensions to the DCOP model have been proposed to enable support of MAS in complex, real-time, and uncertain environments. This survey provides an overview of the DCOP model, offering a classification of its multiple extensions and addressing both resolution methods and applications that find a natural mapping within each class of DCOPs. The proposed classification suggests several future perspectives for DCOP extensions and identifies challenges in the design of efficient resolution algorithms, possibly through the adaptation of strategies from different areas.

Declarative languages offer unprecedented opportunities for the use of parallelism to speed up execution. A declarative language, being not procedural, removes the need to perform operations in a strict order and reduces the number of dependencies among operations, thus opening the doors for concurrent execution. The potential for transparent exploitation of parallelism in logic programming emerged almost immediately with the birth of the paradigm (Pollard 1981).

Abstract Evolutionary Biologists have long struggled with the challenge of developing analysis workflows in a flexible manner, thus facilitating the reuse of phylogenetic knowledge. An evolutionary biology workflow can be viewed as a plan which composes web services that can retrieve, manipulate, and produce phylogenetic trees. The Phylotastic project was launched two years ago as a collaboration between evolutionary biologists and computer scientists, with the goal of developing an open architecture to facilitate the creation of such analysis workflows. While composition of web services is a problem that has been extensively explored in the literature, including within the logic programming domain, the incarnation of the problem in Phylotastic provides a number of additional challenges. Along with the need to integrate preferences and formal ontologies in the description of the desired workflow, evolutionary biologists tend to construct workflows in an incremental manner, by successively refining the workflow, by indicating desired changes (e.g., exclusion of certain services, modifications of the desired output). This leads to the need of successive iterations of incremental replanning, to develop a new workflow that integrates the requested changes while minimizing the changes to the original workflow. This paper illustrates how Phylotastic has addressed the challenges of creating and refining phylogenetic analysis workflows using logic programming technology and how such solutions have been used within the general framework of the Phylotastic project.

This paper proposes a generic approach to planning in the presence of incomplete information. The approach builds on an abstract notion of a belief state representation, along with an associated set of basic operations. These operations facilitate the development of a sound and complete transition function, for reasoning about effects of actions in the presence of incomplete information, and a set of abstract algorithms for planning. The paper demonstrates how the abstract definitions and algorithms can be instantiated in three concrete representations—minimal-DNF, minimal-CNF, and prime implicates—resulting in three highly competitive conformant planners: DNF, CNF, and PIP. The paper relates the notion of a representation to that of ordered binary decision diagrams, a well-known belief state representation employed by many conformant planners, and several target compilation languages that have been presented in the literature.The paper also includes an experimental evaluation of the planners DNF, CNF, and PIP and proposes a new set of conformant planning benchmarks that are challenging for state-of-the-art conformant planners.

This poster highlights a sociocultural analysis of a multifaceted K12 outreach program at New Mexico State University, a Hispanic Serving Institution that has had success recruiting local young women into the computer science department and beyond into the computing workforce. YWiC began in 2006 and has become a rich, extensive outreach program, reaching over 10,200 students across southern New Mexico. Over the years, YWiC has produced strong evaluation results related to computer science knowledge gains and computing interest (see Nesiba, et. Al 2015). The social scientists used Lave and Wenger's (1991) community of practice concept to analyze program design and implementation. Findings show four ways in which the program promotes individual agency, belonging to the local and global computing communities, and "positioning" (Davies and Harre, 1990) of young women as competent computer scientists. Specifically, YWiC: a) makes multiple pathways into computing education and computer science careers via intentional role modeling, b) provides common base knowledge through initial experiences and deep support from multiple role models, c) gives opportunities for young women to identify, and be identified by others as, competent in computing, and d) promotes belonging to a group of like-minded girls with multiple interests.

Abstract This paper explores the use ofAnswer Set Programming (ASP)in solvingDistributed Constraint Optimization Problems (DCOPs). The paper provides the following novel contributions: (1) it shows how one can formulate DCOPs as logic programs; (2) it introduces ASP-DPOP, the first DCOP algorithm that is based on logic programming; (3) it experimentally shows that ASP-DPOP can be up to two orders of magnitude faster than DPOP (its imperative programming counterpart) as well as solve some problems that DPOP fails to solve, due to memory limitations; and (4) it demonstrates the applicability of ASP in a wide array of multi-agent problems currently modeled as DCOPs.

The application of DCOP models to large problems faces two main limitations: (i) Modeling limitations, as each agent can handle only a single variable of the problem; and (ii) Resolution limitations, as current approaches do not exploit the local problem structure withineach agent. This paper proposes a novel Multi-Variable Agent (MVA) DCOP decompositiontechnique, which: (i) Exploits the co-locality of each agent's variables, allowing us to adopt efficient centralized techniques within each agent; (ii) Enables the use of hierarchical parallel models and proposes the use of GPUs; and (iii) Reduces the amount of computation and communication required in several classes of DCOP algorithms.

This paper explores the use of answer set programming (ASP) in solving distributed constraint optimization problems (DCOPs). It makes the following contributions: (i)~It shows how one can formulate DCOPs as logic programs; (ii)~It introduces ASP-DPOP, the first DCOP algorithm that is based on logic programming; (iii)~It experimentally shows that ASP-DPOP can be up to two orders of magnitude faster than DPOP (its imperative-programming counterpart) as well as solve some problems that DPOP fails to solve due to memory limitations; and (iv)~It demonstrates the applicability of ASP in the wide array of multi-agent problems currently modeled as DCOPs.

The paper proposes a condition for preserving the KD45 property of a Kripke model when a sequence of update models is applied to it. The paper defines the notions of a primitive update model and a semi-reflexive KD45 (or sr-KD45) Kripke model. It proves that updating a sr-KD45 Kripke model using a primitive update model results in a sr-KD45 Kripke model, i.e., a primitive update model preserves the properties of a sr-KD45 Kripke model. It shows that several update models for modeling well-known actions found in the literature are primitive. This result provides guarantees that can be useful in presence of multiple applications of actions in multi-agent system (e.g., multi-agent planning).

This paper analyzes the efforts of DISSECT (DIScover SciEnce through Computational Thinking) to introduce computer science theories into K-12 Curricula. This is accomplished by teaching computational thinking (CT) problem solving techniques in existing STEM+C courses in select middle and high school classrooms in Las Cruces, New Mexico, USA. Data collected over the course of the fall 2014 and spring 2015 semesters involving 10 graduate fellows, 9 teachers, and over 200 K-12 students has been analyzed. A single assessment was issued at the beginning and end of each semester in order to track metrics about fellow-teacher pairings, student understanding of CT concepts, and student interest in STEM+C areas. Using statistical analysis software to evaluate the data, we were able to determine the efficacy of the DISSECT program. In particular, we use descriptive statistics to evaluate the trends in CT vocabulary recognition and overall interest in computing, and we compare trends across courses and grade levels.

Computational Thinking (CT) introduces computing concepts and demonstrates their usefulness in many other disciplines. CT principles such as algorithmic problem solving, abstraction, modeling and simulation, are integrated into existing STEM (Science, Technology, Engineering, Mathematics) curricula by DISSECT (DIScover SciEnce through Computational Thinking). By pairing a local K-12 teacher with a graduate fellow, DISSECT provides instruction and resources as instruments that are pertinent to each specific discipline. These skills in problem-solving and abstract reasoning are necessary for students to be able to compete in the modern and future job markets. DISSECT works to provide these skill-sets to students and classrooms that lack access to computers. The K-12 teachers and graduate fellows work together to develop modules that are capable of teaching CT concepts that are directly tied to their current curriculum while removing the need for access to computer systems. This paper will focus on the modules developed and executed in middle and high school classrooms, emphasizing the creative ways explored to operate in a computer-free environment discussing the strengths and weaknesses of different approaches, while qualitatively assessing student engagement, learning, and interaction which is gathered through teacher interviews, observations and informal talks with students.

Young Women in Computing (YWiC) is an outreach initiative housed in the Department of Computer Science at New Mexico State University (NMSU). The program is designed to increase the number of women introduced to computer science; promote the role and presence of women in the field of computing; improve the retention of female students in computing programs; establish a permanent infrastructure (i.e., pipeline) to promote the participation of women, especially of Hispanic heritage, in computing activities; and, serve as a model of effective computer science outreach practices to reach young women. Since 2006, YWiC programming has reached over 10,200 students. By enhancing interest in computing among student populations, YWiC has successfully created a pipeline into Computer Science and Science, Technology, Engineering, and Mathematics (STEM-C) undergraduate programs, particularly at NMSU; among the 366 non-repeated summer campers, 99% of the 98 high school graduates attended college in the fall term immediately following their graduation, with 61% declaring a major in a STEM-C field. This paper will present quality practices and lessons that YWiC has learned in order to become a successful and sustainable outreach program in southern New Mexico.

DISSECT (DIScover SciEnce through Computational Thinking) is a project aimed at introducing students to computer science principles by establishing computational thinking (CT) as a problem-solving technique within middle school and high school Science, Technology, Engineering, and Mathematics (STEM) courses. While DISSECT has shown successful integration of CT into middle school and high school STEM curricula, illustrating the pervasive nature of CT, a question remained; “can CT also be infused into humanities courses (e.g., English, Art, History) in addition to scientific courses (e.g., Chemistry, Biology, Computer Science)?” The answer is positive. The objective of this paper is to present one approach to bridge the gap between CT and humanities through the curriculum of a 12th-grade English Literature course. The course blends CT practices with composition and literature to provide students with the ability to write critical and comparative analyses of selected literature. This paper will describe multiple modules that integrate computational thinking into the course, and discuss the results and assessment tools used to measure student competency in computational thinking.

This paper summarizes the successes and challenges encountered during the incorporation of the New Mexico State University DISSECT (DIScovering SciEnce through Computational Thinking) Fellowship program into a 6th grade classroom. Graduate student fellows work with experienced K-12 teachers to create and deploy interactive computational thinking (CT) modules in middle and high school classrooms that promote active learning through the use of technology and cutting edge scientific research. One of the main objectives of the DISSECT program is to facilitate the professional development of graduate students in computing-rich fields, such as engineering, computer science, and biology, through leadership development, public speaking experience, and an enhanced vision of how CT is vital to in all scientific disciplines. The alliances formed between K-12 teachers and their fellows provide an opportunity for teachers to attain knowledge of CT principles and equips them with the ability to develop and continue their own future lesson plans integrating CT. This paper thoroughly describes specific modules that integrate CT concepts into the traditional 6th grade science curriculum, the statistical results of assessments gauging the development of CT skills and knowledge during the course of one academic year, and suggestions for improvements and incorporation into other curricula.

This paper explores the use of Binary Decision Diagrams (BDDs) in Conformant Planning. A conformant planner, called BPA, based on the BDD representation for belief sets is developed. Heuristics that fit with the BDD representation are presented and analyzed experimentally. The paper confirms the strong potential of BDDs to enhance performance of heuristic search based conformant planners.

This paper provides a novel perspective in the protein structure prediction (PSP) problem. The PSP problem focuses on determining putative 3D structures of a protein starting from its primary sequence. The proposed approach relies on a multi-agent system (MAS) perspective, where concurrent agents explore the folding of different parts of a protein. The strength of the approach lies in the agents’ ability to apply different types of knowledge, expressed in the form of declarative constraints, to prune the search space of folding alternatives. The paper makes also an important contribution in demonstrating the suitability of a general-purpose graphical processing unit approach to implement such MAS infrastructure, with significant performance improvements over the sequential implementation and other methods.

The parallel computing power offered by graphic processing units (GPUs) has been recently exploited to support general purpose applications – by exploiting the availability of general API and the single-instruction multiple-thread-style parallelism present in several classes of problems (e.g. numerical simulations and matrix manipulations) – where relatively simple computations need to be applied to all items in large sets of data. This paper investigates the use of GPUs in parallelising a class of search problems, where the combinatorial nature leads to large parallel tasks and relatively less natural symmetries. Specifically, the investigation focuses on the well-known satisfiability testing (SAT) problem and on the use of the NVIDIA compute unified device architecture, one of the most popular platforms for GPU computing. The paper explores ways to identify strong sources of GPU-style parallelism from SAT solving. The paper describes experiments with different design choices and evaluates the results. The outcomes demonstrate the potential for this approach, leading to one order of magnitude of speedup using a simple NVIDIA platform.

Constraint programming has gained prominence as an effective and declarative paradigm for modeling and solving complex combinatorial problems. Techniques based on local search have proved practical to solve real-world problems, providing a good compromise between optimality and efficiency. In spite of the natural presence of concurrency, there has been relatively limited effort to use novel massively parallel architectures, such as those found in modern Graphical Processing Units (GPUs), to speedup local search techniques in constraint programming. This paper describes a novel framework which exploits parallelism from a popular local search method (the Large Neighborhood Search method), using GPUs.

There is a growing literature demonstrating the importance of collaboration and teamwork in the process of learning computational thinking and the foundational aspects of computer science. While Collaborative Virtual Environments are becoming widespread in the software development professional domain and in various areas of advanced learning, their use in the introductory stages of learning computing is still very limited. On the other hand, in recent years, there has been a blooming of attractive programming environments specifically designed to expose young students (e.g., middle school age) to computational thinking. Alice is a very popular introductory programming environment, focused on programming through animations and story-telling. This paper introduces a novel extension of the Alice framework that enables interaction and collaboration among students in the development of programs. In particular, the new version of Alice described in this paper provides support for virtual pair programming. The modified version of Alice allows two students to remotely share a virtual world, and interact in its construction; the system supports roles assignments, to allow teachers to control activities and contributions of the two students in the creation of a programming project.

This paper presents a universally-designed web-based Workspace that facilitates the manipulation of elementary level mathematics: arithmetic and algebra. The Workspace features a multi-layer design that supports diversity along different dimensions: students with different degrees of visual acuity (from sighted to blind); different levels of proficiency in the subject; and different interaction modes. The universally designed workspace meant to be used in mainstream schools, where an increasing level of inclusion of students with visual impairments has been taking place recently.

This paper summarizes the design and preliminary outcomes from the deployment of the DISSECT (Discovering SciencE through Computational Thinking) project. The project has two primary objectives. On one hand, it aims to revitalize the teaching of traditional K-12 science concepts through the introduction of tools and concepts drawn from the field of computing, enabling the use of interactive and constructive methods to exemplify and explore scientific materials. On the other hand, the project explores how the teaching of sciences could become a vehicle to engage students in the learning of computational thinking, stimulating their interest towards this discipline and providing them with a baseline preparation to facilitate access and success in more formal computer science courses.

This paper presents four novel approaches to enhance efficiency and effectiveness of Inductive Logic Programming (ILP) systems, along with their implementation in a new ILP system, called TWEETY. The proposed approaches include (1) a new declaration mechanism, called connection declarations, for bottom clause construction, which is simpler but more expressive than the commonly used mode declarations; (2) a new covering technique, called super_covering, which reduces the examples in such a way that recursion can be learned, independently from the ordering of the examples; (3) a new search heuristics, called neg_coverage heuristics, which guides the search using only the number of negative examples covered by each hypothesis and (4) a new search algorithm, called doubly_guided_search, which searches for best clauses by alternating the use of two search heuristics, i.e. the traditional coverage search heuristics and the new neg_coverage search heuristics. The TWEETY system is shown to be more effective and efficient than the state-of-the-art ILP system ALEPH; the proposed techniques can be used to enhance efficiency and effectiveness of ALEPH and other systems based on the same ILP principles.

The article introduces a logical framework for negotiation among dishonest agents. The framework relies on the use of abductive logic programming as a knowledge representation language for agents to deal with incomplete information and preferences. The article shows how intentionally false or inaccurate information of agents can be encoded in the agents' knowledge bases. Such disinformation can be effectively used in the process of negotiation to have desired outcomes by agents. The negotiation processes are formulated under the answer set semantics of abductive logic programming, and they enable the exploration of various strategies that agents can employ in their negotiation. A preliminary implementation has been developed using the ASP-Prolog platform.

This paper provides a novel perspective in the Protein Structure Prediction (PSP) problem. The PSP problem focuses on determining putative 3D structures of a protein starting from its primary sequence. The proposed approach relies on a multi-agents approach, where concurrent agents explore the folding of different parts of a protein. The strength of the approach lies in the agents' ability to apply different types of knowledge (expressed in the form of declarative constraints) to prune the local space of folding alternatives. The paper demonstrates the suitability of a GPU approach to implement such multi-agent infrastructure, with significant improvements in speed and quality of solutions w.r.t. other methods (e.g., based on fragments assembly approaches).

The goal of the DISSECT program is to integrate computational thinking lessons into general education K-12 classrooms via graduate student/teacher partnerships. The idea of combining the teaching of CT with other disciplines is not new and it has taken shape in a variety of recent efforts in the formal education of youth. What is promising and innovative is the approach as it is implemented in K12 DISSECT classrooms. Through a collaborative teaching partnership, teachers gain a new perspective regarding computer science, and in cooperation with graduate students well-versed in computer science concepts, develop lessons and course modules that serve two purposes: 1.) Address K-12 content standards in core disciplines (e.g., language arts, life science) and 2.) Introduce CT concepts, such as abstraction, algorithms, data analysis and modeling. This poster describes ways computational thinking (CT) is taught in general K-12 classrooms in New Mexico through cooperative teaching. Along with their potential to stimulate interest in computing, these pilot modules were viewed by K12 teachers as enhancing disciplinary course content that teachers are charged with teaching (e.g., middle school science, language arts), deemed vital for sustainability in K12 schools by participating teachers. Preliminary data indicate graduate student and teacher satisfaction with cooperative teaching of CT. Next steps for research will involve student level data collection and analysis.

BACKGROUND: Scientists rarely reuse expert knowledge of phylogeny, in spite of years of effort to assemble a great "Tree of Life" (ToL). A notable exception involves the use of Phylomatic, which provides tools to generate custom phylogenies from a large, pre-computed, expert phylogeny of plant taxa. This suggests great potential for a more generalized system that, starting with a query consisting of a list of any known species, would rectify non-standard names, identify expert phylogenies containing the implicated taxa, prune away unneeded parts, and supply branch lengths and annotations, resulting in a custom phylogeny suited to the user's needs. Such a system could become a sustainable community resource if implemented as a distributed system of loosely coupled parts that interact through clearly defined interfaces. RESULTS: With the aim of building such a "phylotastic" system, the NESCent Hackathons, Interoperability, Phylogenies (HIP) working group recruited 2 dozen scientist-programmers to a weeklong programming hackathon in June 2012. During the hackathon (and a three-month follow-up period), 5 teams produced designs, implementations, documentation, presentations, and tests including: (1) a generalized scheme for integrating components; (2) proof-of-concept pruners and controllers; (3) a meta-API for taxonomic name resolution services; (4) a system for storing, finding, and retrieving phylogenies using semantic web technologies for data exchange, storage, and querying; (5) an innovative new service, DateLife.org, which synthesizes pre-computed, time-calibrated phylogenies to assign ages to nodes; and (6) demonstration projects. These outcomes are accessible via a public code repository (GitHub.com), a website (http://www.phylotastic.org), and a server image. CONCLUSIONS: Approximately 9 person-months of effort (centered on a software development hackathon) resulted in the design and implementation of proof-of-concept software for 4 core phylotastic components, 3 controllers, and 3 end-user demonstration tools. While these products have substantial limitations, they suggest considerable potential for a distributed system that makes phylogenetic knowledge readily accessible in computable form. Widespread use of phylotastic systems will create an electronic marketplace for sharing phylogenetic knowledge that will spur innovation in other areas of the ToL enterprise, such as annotation of sources and methods and third-party methods of quality assessment.

This article describes the planner C p A( H ), the recipient of the Best Nonobservable Nondeterministic Planner Award in the “Uncertainty Track” of the 6 th International Planning Competition (IPC), 2008. The article presents the various techniques that help C p A( H ) to achieve the level of performance and scalability exhibited in the competition. The article also presents experimental results comparing C p A( H ) with state-of-the-art conformant planners.

Abstract The paper presents a knowledge representation formalism, in the form of a high-levelAction Description Language (ADL)for multi-agent systems, where autonomous agents reason and act in a shared environment. Agents are autonomously pursuing individual goals, but are capable of interacting through a shared knowledge repository. In their interactions through shared portions of the world, the agents deal with problems of synchronization and concurrency; the action language allows the description of strategies to ensure a consistent global execution of the agents’ autonomously derived plans. A distributed planning problem is formalized by providing the declarative specifications of the portion of the problem pertaining to a single agent. Each of these specifications is executable by a stand-alone CLP-based planner. The coordination among agents exploits a Linda infrastructure. The proposal is validated in a prototype implementation developed in SICStus Prolog.

In this paper we present a web-based system that enables children with impaired vision to handle basic arithmetic knowledge: addition, subtraction, multiplication, and division. Taking into consideration the accommodation of varied levels of vision disability - minor to severe - the new system provides an electronic auditory alternative to the currently used tools.

The paper introduces a novel technique for improving the performance and scalability of best-first progression-based conformant planners. The technique is inspired by different well-known techniques from classical planning, such as landmark and stratification. Its most salient feature is that it is relatively cheap to implement yet quite effective when applicable. The effectiveness of the proposed technique is demonstrated by the development of new conformant planners by integrating the technique in various state-of-the-art conformant planners and an extensive experimental evaluation of the new planners using benchmarks collected from various sources. The result shows that the technique can be applied in several benchmarks and helps improve both performance and scalability of conformant planners.

This paper compares in depth the effectiveness of two conjunctive belief state representations in contingent planning: prime implicates and minimal CNF, a compact form of CNF formulae, which were initially proposed in conformant planning research (To et al. 2010a; 2010b). Similar to the development of the contingent planner CNFct for minimal CNF (To et al. 2011b), the present paper extends the progression function for the prime implicate representation in (To et al. 2010b) for computing successor belief states in the presence of incomplete information to handle non-deterministic and sensing actions required in contingent planning. The idea was instantiated in a new contingent planner, called PIct, using the same AND/OR search algorithm and heuristic function as those for CNFct. The experiments show that, like CNFct, PIct performs very well in a wide range of benchmarks. The study investigates the advantages and disadvantages of the two planners and identifies the properties of each representation method that affect the performance.

This work proposes new approaches to contingent planning using alternative belief state representations extended from those in conformant planning and a new AND/OR forward search algorithm, called PrAO, for contingent solutions. Each representation was implemented in a new contingent planner. The important role of belief state representation has been confirmed by the fact that our planners all outperform other stateof- the-art planners on most benchmarks and the comparison of their performances varies across all the benchmarks even using the same search algorithm PrAO and same unsophisticated heuristic scheme. The work identifies the properties of each representation method that affect the performance.

This paper presents the development of Multimodal Interactive Cubes for Object Orientation (MICOO) manipulatives. This system provides a multimodal tangible user interface (TUI), enabling people with visual impairments to create, modify and naturally interact with diagrams and graphs on a multitouch surface. The system supports a novel notion of active orientation and proximity tracking of manipulatives against diagram and graph components. If the orientation of a MICOO matches a component, then a user is allowed to modify that component by moving the MICOO. Conversely, if a MICOO does not match orientation or is far from a component, audio feedback is activated to help the user reach that component. This will lessen the need for manual intervention, enable independent discovery on the part of the user, and offers dynamic behavior, whereas the representation interacts and provides feedback to the user. The platform has been developed and it is undergoing formal evaluation (e.g., browse, modify and construct graphs on a Cartesian plot and diagrams).

The paper investigates a novel approach, based on Constraint Logic Programming (CLP), to predict potential 3D conformations of a protein via fragments assembly. The fragments are extracted and clustered by a preprocessor from a database of known protein structures. Assembling fragments into a complete conformation is modeled as a constraint satisfaction problem solved using CLP. The approach makes use of a simplified Cα-side chain centroid protein model, that offers efficiency and a good approximation for space filling. The approach adapts existing energy models for protein representation and applies a large neighboring search (LNS) strategy. The results show the feasibility and efficiency of the method, and the declarative nature of the approach simplifies the introduction of additional knowledge and variations of the model.

The paper introduces a logical framework for negotiation among dishonest agents. The framework relies on the use of abductive logic programming as a knowledge representation language for agents to deal with incomplete information and preferences. The paper shows how intentionally false or inaccurate information of agents could be encoded in the agents' knowledge bases. Such disinformation can be effectively used in the process of negotiation to have desired outcomes by agents. The negotiation processes are formulated under the answer set semantics of abductive logic programming and enable the exploration of various strategies that agents can employ in their negotiation.

This paper investigates the effectiveness of two state representations, CNF and DNF, in contingent planning. To this end, we developed a new contingent planner, called CNFct, using the AND/OR forward search algorithm PrAO [To et al., 2011] and an extension of the CNF representation of [To et al., 2010] for conformant planning to handle nondeterministic and sensing actions for contingent planning. The study uses CNFct and DNFct [To et al., 2011] and proposes a new heuristic function for both planners. The experiments demonstrate that both CNFct and DNFct offer very competitive performance in a large range of benchmarks but neither of the two representations is a clear winner over the other. The paper identifies properties of the representation schemes that can affect their performance on different problems.

BACKGROUND: The Comparative Data Analysis Ontology (CDAO) is an ontology developed, as part of the EvoInfo and EvoIO groups supported by the National Evolutionary Synthesis Center, to provide semantic descriptions of data and transformations commonly found in the domain of phylogenetic analysis. The core concepts of the ontology enable the description of phylogenetic trees and associated character data matrices. RESULTS: Using CDAO as the semantic back-end, we developed a triple-store, named CDAO-Store. CDAO-Store is a RDF-based store of phylogenetic data, including a complete import of TreeBASE. CDAO-Store provides a programmatic interface, in the form of web services, and a web-based front-end, to perform both user-defined as well as domain-specific queries; domain-specific queries include search for nearest common ancestors, minimum spanning clades, filter multiple trees in the store by size, author, taxa, tree identifier, algorithm or method. In addition, CDAO-Store provides a visualization front-end, called CDAO-Explorer, which can be used to view both character data matrices and trees extracted from the CDAO-Store. CDAO-Store provides import capabilities, enabling the addition of new data to the triple-store; files in PHYLIP, MEGA, nexml, and NEXUS formats can be imported and their CDAO representations added to the triple-store. CONCLUSIONS: CDAO-Store is made up of a versatile and integrated set of tools to support phylogenetic analysis. To the best of our knowledge, CDAO-Store is the first semantically-aware repository of phylogenetic data with domain-specific querying capabilities. The portal to CDAO-Store is available at http://www.cs.nmsu.edu/~cdaostore.

The ICLP series of conferences provides a technical forum for presenting and disseminating innovative research in the field of logic programming. The 24th International Conference on Logic Programming took place from December 9–13, 2008 in the city of Udine, Italy. The conference attracted 177 submissions and featured a high-quality program focused on the foundations, developments, and applications of logic programming. Of particular significance was the special session celebrating the 20th anniversary of the seminal paper on the stable model semantics.

The paper presents an investigation of the use of two alternative forms of CNF formulae—prime implicates and minimal CNF—to compactly represent belief states in the context of conformant planning. For each representation, we define a transition function for computing the successor belief state resulting from the execution of an action in a belief state; results concerning soundness and completeness are provided. The paper describes a system (PIP) which dynamically selects either of these two forms to represent belief states, and an experimental evaluation of PIP against state-of-the-art conformant planners. The results show that PIP has the potential of scaling up better than other planners in problems rich in disjunctive information about the initial state.

Detecting tables in a spreadsheet is the first step needed to make spreadsheet documents accessible to individuals with visual disabilities. Techniques to enable aural presentation and navigation of tables have been proposed, but they assume a thorough knowledge of the structure of the table; on the other hand, boundaries and structure of tables in a spreadsheet are not evident without a visual exploration. This paper presents an algorithm for table recognition in spreadsheets. The algorithm uses three types of cells as its basis: title cell, header cell, and data cell. Different attributes of the cells are used to identify the cell type within a spreadsheet. Hierarchical clustering is used to aggregate cells to compose the functional components of a table. The algorithm has been evaluated on a diverse set of benchmarks with very encouraging results.

This paper explores the use of Constraint Logic Programming (CLP) as a platform for experimenting with planning problems in the presence of multiple interacting agents. The paper develops a novel constraint-based action language, ℬMAP , that enables

Abstract The logics of knowledge are modal logics that have been shown to be effective in representing and reasoning about knowledge in multi-agent domains. Relatively few computational frameworks for dealing with computation of models and useful transformations in logics of knowledge (e.g., to support multi-agent planning with knowledge actions and degrees of visibility) have been proposed. This paper explores the use of logic programming (LP) to encode interesting forms of logics of knowledge and compute Kripke models. The LP modeling is expanded with useful operators on Kripke structures, to support multi-agent planning in the presence of both world-altering and knowledge actions. This results in the first ever implementation of a planner for this type of complex multi-agent domains.

Abstract Action description languages, such as and ℬ (Gelfond and Lifschitz,Electronic Transactions on Artificial Intelligence, 1998, vol. 2, pp. 193—210), are expressive instruments introduced for formalizing planning domains and planning problem instances. The paper starts by proposing a methodology to encode an action language (with conditional effects and static causal laws), a slight variation of ℬ, usingConstraint Logic Programming over Finite Domains. The approach is then generalized to raise the use of constraints to the level of the action language itself. A prototype implementation has been developed, and the preliminary results are presented and discussed.

Abstract The paper investigates a novel approach, based on Constraint Logic Programming (CLP), to predict the 3D conformation of a protein via fragments assembly. The fragments are extracted by a preprocessor—also developed for this work—from a database of known protein structures that clusters and classifies the fragments according to similarity and frequency. The problem of assembling fragments into a complete conformation is mapped to a constraint solving problem and solved using CLP. The constraint-based model uses a medium discretization degree Cα-side chain centroid protein model that offers efficiency and a good approximation for space filling. The approach and adapts existing energy models to the protein representation used and applies a large neighboring search strategy. The results shows the feasibility and efficiency of the method. The declarative nature of the solution allows to include future extensions, e.g., different size fragments for better accuracy.

Several solutions, based on aural and haptic feedback, have been developed to enable access to complex on-line information for people with visual impairments. Nevertheless, there are several components of widely used software applications that are still beyond the reach of screen readers and Braille displays.

This paper describes the Young Women in Computing program, an ongoing outreach program in Computer Science at New Mexico State University (NMSU). Features of the program include summer camps and academic year activities, computing in context, peer mentoring, and role models. The main goal is to increase interest in computing among female high school students. The paper discusses lessons learned from three years of experience with the program.

Abstract The goal of this paper is to investigate the application of parallel programming techniques to boost the performance of heuristic search‐based planning systems in various aspects. It shows that an appropriate parallelization of a sequential planning system often brings gain in performance and/or scalability. We start by describing general schemes for parallelizing the construction of a plan. We then discuss the applications of these techniques to two domain‐independent heuristic search‐based planners—a competitive conformant planner (CPA) and a state‐of‐the‐art classical planner (FF). We present experimental results—on both shared memory and distributed memory platforms—which show that the performance improvements and scalability are obtained in both cases. Finally, we discuss the issues that should be taken into consideration when designing a parallel planning system and relate our work to the existing literature. Copyright © 2009 John Wiley & Sons, Ltd.

In recent years, Answer Set Programming has gained popularity as a viable paradigm for applications in knowledge representation and reasoning. This paper presents a novel methodology to compute answer sets of an answer set program. The proposed methodology maintains a bottom-up approach to the computation of answer sets (as in existing systems), but it makes use of a novel structuring of the computation, that originates from the non-ground version of the program. Grounding is lazily performed during the computation of the answer sets. The implementation has been realized using Constraint Logic Programming over finite domains.

This paper presents experimental comparisons between the declarative encodings of various computationally hard problems in Answer Set Programming (ASP) and Constraint Logic Programming over Finite Domains (CLP(FD)). The objective is to investigate how solvers in the two domains respond to different problems, highlighting the strengths and weaknesses of their implementations, and suggesting criteria for choosing one approach over the other. Ultimately, the work in this paper is expected to lay the foundations for a transfer of technology between the two domains, for example by suggesting ways to use CLP(FD) in the execution of ASP.

This article presents a distributed version of the adjSolver algorithm for computing the answer sets of logic programs. adjSolver operates a classical branch-and-bound structure; its intrinsic parallelism is exploited to control, with a centralized architecture, the delegation of promising search subspaces to distributed handling agents. adjSolver has been implemented and tested on a Beowulf platform, using MPI message passing. The communication overhead was minimized by adopting a compact representation of the data exchanged among agents and by reusing previously-computed partial solutions.

Abstract The paper introduces the notion of offline justification for answer set programming (ASP). Justifications provide a graph-based explanation of the truth value of an atom with respect to a given answer set. The paper extends also this notion to provide justification of atoms during the computation of an answer set (on-line justification) and presents an integration of online justifications within the computation model of Smodels. Offline and online justifications provide useful tools to enhance understanding of ASP, and they offer a basic data structure to support methodologies and tools for debugging answer set programs. A preliminary implementation has been developed in – .

In this paper, we present a new approach, called NM-ILP-IP, for inductive learning in the context of nonmonotonic logic frameworks. This approach is based on the notations of concept instances and instance patterns introduced in [13]. When a strictly correct Horn theory cannot be induced, this approach induces a normal logic program, by specializing a previously learned overly-general theory. The advantages of this approach over others include: (a) it does not rely on existing ILP systems, and it avoids many of the effectiveness and efficiency drawbacks of ordinary ILP systems; (b) no theorem prover is needed during the learning process; (c) it introduces negation as failure (NAF) of existing predicates and introduces new abnormality predicates only when necessary, making the final theory more compact.

In this paper, we present two alternative approaches to defining answer sets for logic programs with arbitrary types of abstract constraint atoms (c-atoms). These approaches generalize the fixpoint-based and the level mapping based answer set semantics of normal logic programs to the case of logic programs with arbitrary types of c-atoms. The results are four different answer set definitions which are equivalent when applied to normal logic programs. The standard fixpoint-based semantics of logic programs is generalized in two directions, called answer set by reduct and answer set by complement. These definitions, which differ from each other in the treatment of negation-as-failure (naf) atoms, make use of an immediate consequence operator to perform answer set checking, whose definition relies on the notion of conditional satisfaction of c-atoms w.r.t. a pair of interpretations. The other two definitions, called strongly and weakly well-supported models, are generalizations of the notion of well-supported models of normal logic programs to the case of programs with c-atoms. As for the case of fixpoint-based semantics, the difference between these two definitions is rooted in the treatment of naf atoms. We prove that answer sets by reduct (resp. by complement) are equivalent to weakly (resp. strongly) well-supported models of a program, thus generalizing the theorem on the correspondence between stable models and well-supported models of a normal logic program to the class of programs with c-atoms. We show that the newly defined semantics coincide with previously introduced semantics for logic programs with monotone c-atoms, and they extend the original answer set semantics of normal logic programs. We also study some properties of answer sets of programs with c-atoms, and relate our definitions to several semantics for logic programs with aggregates presented in the literature.

Abstract This paper presents the design, implementation and application of a constraint programming framework on 3D crystal lattices. The framework provides the flexibility to express and resolve constraints dealing with structural relationships of entities placed in a 3D lattice structure in space. Both sequential and parallel implementations of the framework are described, along with experiments that highlight its superior performance with respect to the use of more traditional frameworks (e.g. constraints on finite domains and integer programming) to model lattice constraints. The framework is motivated and applied to address the problem of solving the protein folding prediction problem, i.e. predicting the 3D structure of a protein from its primary amino acid sequence. Results and comparison with performance of other constraint‐based solutions to this problem are presented. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract This paper describes the development of thePALSsystem, an implementation of Prolog capable of efficiently exploiting or-parallelism ondistributed-memoryplatforms—specifically Beowulf clusters. PALS makes use of a novel technique, calledincremental stack-splitting. The technique proposed builds on the stack-splitting approach, previously described by the authors and experimentally validated on shared-memory systems, which in turn is an evolution of the stack-copying method used in a variety of parallel logic and constraint systems—e.g., MUSE, YAP, and Penny. The PALS system is the first distributed or-parallel implementation of Prolog based on the stack-splitting method ever realized. The results presented confirm the superiority of this method as a simple yet effective technique to transition from shared-memory to distributed-memory systems. PALS extends stack-splitting by combining it with incremental copying; the paper provides a description of the implementation of PALS, including details of how distributed scheduling is handled. We also investigate methodologies to effectively support order-sensitive predicates (e.g., side-effects) in the context of the stack-splitting scheme. Experimental results obtained from running PALS on both Shared Memory and Beowulf systems are presented and analyzed.

Abstract This technical note describes a monotone and continuous fixpoint operator to compute the answer sets of programs with aggregates. The fixpoint operator relies on the notion ofaggregate solution. Under certain conditions, this operator behaves identically to the three-valued immediate consequence operator ΦaggrPfor aggregate programs, independently proposed in Pelov (2004) and Pelovet al.(2004). This operator allows us to closely tie the computational complexity of the answer set checking and answer sets existence problems to the cost of checking a solution of the aggregates in the program. Finally, we relate the semantics described by the operator to other proposals for logic programming with aggregates.

Computer and Information Technologies have redesigned the way modern society operates. In particular, they have identified new avenues to provide tools and resources to alleviate the traditional ba...

The unification problem in algebras capable of describing sets has been tackled, directly or indirectly, by many researchers and it finds important applications in various research areas, e.g. deductive databases, theorem proving, static analysis, rapid software prototyping. The various solutions proposed are spread across a large literature. In this paper we provide a uniform presentation of unification of sets, formalizing it at the level of set theory. We address the problem of deciding existence of solutions at an abstract level. This provides also the ability to classify different types of set unification problems. Unification algorithms are uniformly proposed to solve the unification problem in each of such classes. The algorithms presented are partly drawn from the literature – and properly revisited and analyzed – and partly novel proposals. In particular, we present a new goal-driven algorithm for general unification.

We present a declarative language, ${\cal PP}$ , for the high-level specification of preferences between possible solutions (or trajectories) of a planning problem. This novel language allows users to elegantly express non-trivial, multi-dimensional preferences and priorities over such preferences. The semantics of ${\cal PP}$ allows the identification of most preferred trajectories for a given goal. We also provide an answer set programming implementation of planning problems with ${\cal PP}$ preferences.

The paper describes a constraint-based solution to the protein folding problem on face-centered cubic lattices---a biologically meaningful approximation of the general protein folding problem. The paper improves the results presented in [15] and introduces new ideas for improving efficiency: (i) proper reorganization of the constraint structure; (ii) development of novel, both general and problem-specific, heuristics; (iii) exploitation of parallelism. Globally, we obtain a speed up in the order of 60 w.r.t. [15]. We show how these results can be employed to solve the folding problem for large proteins containing subsequences whose conformation is already known.

We describe the UMA system, a system developed under a multi-institution collaboration for making mathematics universally accessible. The UMA system includes translators that freely inter-convert mathematical documents transcribed in formats used by unsighted individual (Nemeth, Marburg) to those used by sighted individuals (LaTeX, Math-ML, OpenMath) and vice versa. The UMA system also includes notation-independent tools for aural navigation of mathematics. In this paper, we give an overview of the UMA system and the techniques used for realizing it.

This paper shows how action theories, expressed in an extended version of the language , can be naturally encoded using Prioritized Default Theory. We also show how prioritized default theory can be extended to express preferences between rules. This extension provides a natural framework to introduce different types of preferences in action theories—preferences between actions and preferences between final states. In particular, we demonstrate how these preferences can be expressed within extended prioritized default theory. We also discuss how this framework can be implemented in terms of answer set programming.

In this paper, we highlight the main research directions currently pursued by the investigators for the development of new tools to improve Web accessibility for users with visual disabilities. The overall principle is to create intelligent software agents used to assist visually impaired individuals in accessing complex on-line data organizations (e.g. tables, frame structures) in a meaningful way. Accessibility agents make use of knowledge representation structures (automatically or manually derived) to assist users in developing navigation plans; these are employed to locate given pieces of information or to answer user's desired goals.

In this paper we propose a semantically well-founded combination of the constraint solvers used in the constraint programming languages CLP(SET) and CLP(FD). This work demonstrates that it is possible to provide efficient executions (through CLP(FD) solvers) while maintaining the expressive power and flexibility of the CLP(SET) language. We develop a combined constraint solver and we show how static analysis can help in organizing the distribution of constraints to the two constraint solvers.

In this paper, we provide a progress report on the development of technology to support the non-visual navigation of complex HTML and XML structures.

In this paper we demonstrate how the DSL for Table navigation [16] can be reinterpreted in the context of an action theory [8]. We also show how this generalization provides the ability to carry out more complex tasks such as (i) allowing the user to describe the objective of his/her navigation as a goal and let automatic mechanisms (i.e., a planner) develop (part of) the navigation process; and (ii) allowing the semantic description to predefine not only complete navigation strategies (as in [16]) but also partial skeletons, making the remaining part of the navigation dependent on run-time factors, e.g., user's goals, specific aspects of the table's content, User's run-time decisions.

Incremental stack-copying is a technique which has been successfully used to support efficient parallel execution of a variety of search-based Al systems-e.g., logic-based and constraint-based systems. The idea of incremental stack-copying is to only copy the difference between the data areas of two agents, instead of copying them entirely, when distributing parallel work. In order to further reduce the communication during stack-copying and make its implementation efficient on message-passing platforms, a new technique, called stack-splitting, has recently been proposed. In this paper, we describe a scheme to effectively combine stack-splitting with incremental stack copying, to achieve superior parallel performance in a non-shared memory environment. We also describe a scheduling scheme for this incremental stack-splitting strategy. These techniques are currently being implemented in the PALS system-a parallel constraint logic programming system.

In this paper we study the use of parallelism to speed up execution of Answer Set Programs (ASP). ASP is an emerging programming paradigm which combines features from constraint programming, logic programming, and non-monotonic reasoning, and has found relevant applications in areas such as planning and intelligent agents. We propose different methodologies to parallelize execution of ASP programs, and we describe a prototype which exploits one of such forms of parallelism (vertical parallelism). Performance figures are presented and analyzed along with various considerations regarding scheduling and optimization.

Abstract Naive parallel implementation of non‐deterministic systems (such as a theorem proving system) and languages (such as logic, constraint, or concurrent constraint languages) can result in poor performance. We present three optimization schemas, based onflattening of the computation tree,procrastination of overheads, andsequentialization of computationsthat can be systematically applied to parallel implementations of non‐deterministic systems/languages to reduce the parallel overhead and to obtain improved efficiency of parallel execution. The effectiveness of these schemas is illustrated by applying them to the ACE parallel logic programming system. The performance data presented show that considerable improvement in execution efficiency can be achieved. Copyright © 2001 John Wiley & Sons, Ltd.

Since the early days of logic programming, researchers in the field realized the potential for exploitation of parallelism present in the execution of logic programs. Their high-level nature, the presence of nondeterminism, and their referential transparency, among other characteristics, make logic programs interesting candidates for obtaining speedups through parallel execution. At the same time, the fact that the typical applications of logic programming frequently involve irregular computations, make heavy use of dynamic data structures with logical variables, and involve search and speculation, makes the techniques used in the corresponding parallelizing compilers and run-time systems potentially interesting even outside the field. The objective of this article is to provide a comprehensive survey of the issues arising in parallel execution of logic programming languages along with the most relevant approaches explored to date in the field. Focus is mostly given to the challenges emerging from the parallel execution of Prolog programs. The article describes the major techniques used for shared memory implementation of Or-parallelism, And-parallelism, and combinations of the two. We also explore some related issues, such as memory management, compile-time analysis, and execution visualization.

In this paper, we present an implementation model which efficiently supports backtracking in an independent and-parallel nondeterministic system. The problem is tackled in the context of logic programming, although the solution proposed is sufficiently general to be easily extended to different nondeterministic systems, such as constraint programming systems. The complexity of the problem is demonstrated by the fact that most existing and-parallel systems either do not support backtracking over and-parallel calls or simply avoid analyzing the performance of their systems in the presence of nondeterministic benchmarks. The implementation model we present is an extension of the backtracking scheme developed by Hermenegildo and Nasr (1986) and relies on a novel memory organization scheme and on the use of various optimizations to reduce communication and overhead. The solution developed has been implemented in the ACE Parallel Prolog system. The performance of the system is analyzed on a variety of benchmarks. The results obtained are remarkable: speedups achieved during forward execution are not lost in heavy backtracking activities and, frequently, super-linear speedups are obtained thanks to a semi-intelligent backtracking scheme.

We present a general framework for navigating complex structures - specifically, tables, frames, and forms?found in web-pages. Our framework is based on an (automatically or manually created) program written in a domain specific language that captures the semantic structure of the table/frame/form as well as specifies the strategy to be used for navigating it. We describe our general framework and the domain specific language we have designed.

In this paper we present a study of the problem of handling constraints made by conjunctions of positive and negative literals based on the predicate symbols =, ∈,∪ and || (i.e., disjointness of two sets) in a (hybrid) universe of finite sets . We also review and compare the main techniques considered to represent finite sets in the context of logic languages. The resulting contraint algorithms are embedded in a Constraint Logic Programming (CLP) language which provides finite sets—along with basic set-theoretic operations—as first-class objects of the language. The language—called CLP( SET )—is an instance of the general CLP framework, and as such it inherits all the general features and theoretical results of this scheme. We provide, through programming examples, a taste of the expressive power offered by programming in CLP( SET ).

We study the problem of exploiting parallelism from search-based AI systems on distributed machines. We propose stack-splitting, a technique for implementing or-parallelism, which when coupled with appropriate scheduling strategies leads to: (i) reduced communication during distributed execution; and, (ii) distribution of larger grain- sized work to processors. The modified technique can also be implemented on shared memory machines and should be quite competitive with existing methods. Indeed, an implementation has been carried out on shared memory machines, and the results are reported here.

We show how parallelizing compilers can be automatically derived from denotational definitions of programming languages. In our approach, the denotational definition is expressed using definite clause grammars (syntax specification) and Horn Logic or Constraint Logic (semantic specification). The conditions for executing two or more statements in parallel (e.g. GCD test, Banerjee test, or exact test) are included as part of the parallel denotational semantics of the language. Solutions of Diophantine equations, needed for parallelizing DO loops, can be expressed in constraint logic as well, and are thus easily incorporated in our denotational framework. This parallel denotational specification of the language is executable, and thus automatically yields a parallel interpreter. This interpreter can be partially evaluated with respect to a given program to automatically obtain (provably correct) parallel compiled code. In addition, the various syntactic and semantic restructuring transformations that have been proposed to expose more parallelism in sequential programs can also be expressed in our denotational framework.

We consider the problem of efficiently supporting backtracking in independent and-parallel non-deterministic systems. We consider this problem in the context of logic programming, although the solution proposed is sufficiently general to be applicable to any non-deterministic language or system. Our model employs various optimizations, as well as a novel memory organization scheme in which processors are allowed to traverse each others' stacks to achieve this efficiency. The solution developed has been implemented in the ACE Prolog system. The performance of the system is analyzed on a variety of non-deterministic benchmarks.

The development of the World Wide Web (WWW) has been considerably delayed due to the excessive complexity of developing advanced and intelligent applications for the Internet. An average application may require the use of different languages, an in-depth understanding of various communication protocols and low-level communication mechanisms, etc. We propose a logic programming system, called W-ACE, extended with various features to support natural and efficient development of Internet tools. The nature of the constructs introduced makes it particularly suitable to support intelligent Internet applications (knowledge-based systems, agents, etc.). W-ACE covers various issues in supporting knowledge-based handling of the World Wide Web, allowing structured and constraint-based management of WWW information, passive and active views of WWW, as well as a powerful support for concurrent applications. Various examples of complex intelligent applications are presented, to underline the simplicity and the power of the proposed ideas.

We develop a general constraint logic programming (CLP) based framework for specification and verification of real time systems. Our framework is based on the notion of timed automata that have traditionally been used for specifying real time systems. In our framework, a user models the ordering of real time events as the grammar of a language accepted by a timed automata, the real time constraints on these events are then captured as denotations of the grammar productions specified by the user. The grammar can be specified as a Definite Clause Grammar (DCG), while the denotations can be specified in constraint logic. The resulting specification can hence be regarded as a constraint logic program (CLP), and is executable. Many interesting properties of the real time system can be verified by posing appropriate queries to this CLP program. A major advantage of our approach is that it is constructive in nature, i.e., it can be used for computing the conditions under which a property will hold for a given real time system. Our framework also suggests new types of formalisms that we call constraint automata and timed push down automata.