# KR&R Group: Publications

Excellent! Next, you can

**embed**this page using one of several options.To the site owner:

**Action required!** Mendeley is changing its
API. In order to keep using Mendeley with BibBase past April
14th, you need to:

- renew the authorization for BibBase on Mendeley, and
- update the BibBase URL in your page the same way you did when you initially set up this page.

2011
(8)

Computing Weighted Solutions in ASP: Representation-Based Method vs. Search-Based Method.
Cakmak, D.; Erdem, E.; and Erdogan, H.

Link N bibtex abstract

*Annals of Mathematics and Artificial Intelligence (AMAI)*. 2011.Link N bibtex abstract

@article{amai11, ee = {http://dx.doi.org/10.1007/s10472-011-9242-1}, urln = {amai11.pdf}, author = {Duygu Cakmak and Esra Erdem and Halit Erdogan}, title = {Computing Weighted Solutions in ASP: Representation-Based Method vs. Search-Based Method}, journal = {Annals of Mathematics and Artificial Intelligence (AMAI)}, abstract = {For some problems with too many solutions, one way to obtain the more desirable solutions is to assign each solution a weight that characterizes its importance quantitatively, and then compute the solutions whose weights are over (resp. below) a given threshold. This paper studies computing weighted solutions for a given computational problem, in the context of Answer Set Programming (ASP). In particular, we investigate two sorts of methods for computing weighted solutions: one method suggests modifying the ASP representation of the problem to compute weighted solutions using an existing ASP solver and the other suggests modifying the search algorithm of the answer set solver to compute weighted solutions incrementally. The applicability of these methods are shown on two sorts of problems: reconstructing weighted phylogenies (for Indo-European languages and for Quercus species) and finding weighted plans (for Blocks World planning problems). In the experiments with the representation-based method, the answer set solver CLASP is used and weight functions are represented in ASP. For the search-based method, the algorithm of CLASP is modified (the modified solver is called CLASP-W) and weight functions are implemented in C++. For phylogenies, two weight functions are introduced by incorporating domain-specific information about groupings of species; one of them cannot be represented in ASP due to some mathematical functions not supported by the ASP solvers. For plans, we define a weight function that characterizes the total cost of executing actions in a plan. In these experiments the following are observed. With weight measures that can be represented in ASP, the search-based method outperforms the representation-based method in terms of computational efficiency (both time and space). With weight functions that cannot be represented in ASP, the search-based method provides a tool for computing weighted solutions in ASP. The search-based method can be applied to different domains, without modifying the algorithm of CLASP-W; in that sense, the search-based method is modular and can be useful to other ASP applications. With either method, plausible phylogenies among many can be found without computing all phylogenies and requiring historical linguists to go over them manually, and less costly plans can be found without computing all plans; in that sense, our methods contribute to phylogenetics and AI planning studies as well.}, year = {2011} }

For some problems with too many solutions, one way to obtain the more desirable solutions is to assign each solution a weight that characterizes its importance quantitatively, and then compute the solutions whose weights are over (resp. below) a given threshold. This paper studies computing weighted solutions for a given computational problem, in the context of Answer Set Programming (ASP). In particular, we investigate two sorts of methods for computing weighted solutions: one method suggests modifying the ASP representation of the problem to compute weighted solutions using an existing ASP solver and the other suggests modifying the search algorithm of the answer set solver to compute weighted solutions incrementally. The applicability of these methods are shown on two sorts of problems: reconstructing weighted phylogenies (for Indo-European languages and for Quercus species) and finding weighted plans (for Blocks World planning problems). In the experiments with the representation-based method, the answer set solver CLASP is used and weight functions are represented in ASP. For the search-based method, the algorithm of CLASP is modified (the modified solver is called CLASP-W) and weight functions are implemented in C++. For phylogenies, two weight functions are introduced by incorporating domain-specific information about groupings of species; one of them cannot be represented in ASP due to some mathematical functions not supported by the ASP solvers. For plans, we define a weight function that characterizes the total cost of executing actions in a plan. In these experiments the following are observed. With weight measures that can be represented in ASP, the search-based method outperforms the representation-based method in terms of computational efficiency (both time and space). With weight functions that cannot be represented in ASP, the search-based method provides a tool for computing weighted solutions in ASP. The search-based method can be applied to different domains, without modifying the algorithm of CLASP-W; in that sense, the search-based method is modular and can be useful to other ASP applications. With either method, plausible phylogenies among many can be found without computing all phylogenies and requiring historical linguists to go over them manually, and less costly plans can be found without computing all plans; in that sense, our methods contribute to phylogenetics and AI planning studies as well.

Incorporating HADAMAC experiment into NVR for NMR Structure-Based Assignments.
Halit Erdogan, undefined; and Apaydin, M. S.
In

N bibtex abstract

*Proc. of the 6th International Symposium on Health Informatics and Bioinformatics (HIBIT'11)*, 2011.N bibtex abstract

@inproceedings{hibit11, author = {Halit Erdogan, and Mehmet Serkan Apaydin}, title = {Incorporating HADAMAC experiment into NVR for NMR Structure-Based Assignments}, booktitle = {Proc. of the 6th International Symposium on Health Informatics and Bioinformatics (HIBIT'11)}, year = {2011}, urlN ={hibit11.pdf}, abstract = {Protein structure determination is crucial to understand a protein's function and to develop drugs against diseases. Nuclear Magnetic Resonance (NMR) spectroscopy is an experimental technique that allows one to study protein structure in solution. In NMR Structure-based assignment problem, the aim is to assign experimentally observed peaks to the specific nuclei of the target molecule by using a template protein and it is an important computational challenge. NVR-BIP is a tool that utilizes a scoring function based on NVR's framework and computes assignments for given NMR data. In this paper, we incorporate HADAMAC experiment---which helps predict an amino acid class for each peak--- with NVRBIP's scoring function. Experiments show that the new scoring function results in higher assignment accuracies compared to the previous approaches}, }

Protein structure determination is crucial to understand a protein's function and to develop drugs against diseases. Nuclear Magnetic Resonance (NMR) spectroscopy is an experimental technique that allows one to study protein structure in solution. In NMR Structure-based assignment problem, the aim is to assign experimentally observed peaks to the specific nuclei of the target molecule by using a template protein and it is an important computational challenge. NVR-BIP is a tool that utilizes a scoring function based on NVR's framework and computes assignments for given NMR data. In this paper, we incorporate HADAMAC experiment---which helps predict an amino acid class for each peak--- with NVRBIP's scoring function. Experiments show that the new scoring function results in higher assignment accuracies compared to the previous approaches

Generating Explanations for Complex Biomedical Queries.
Oztok, U.; and Erdem, E.
In

N bibtex abstract

*Proc. of the 25th AAAI Conference on Artificial Intelligence (AAAI'11)*, 2011.N bibtex abstract

@inproceedings{aaaiSA11, author = {Umut Oztok and Esra Erdem}, title = {Generating Explanations for Complex Biomedical Queries}, booktitle = {Proc. of the 25th AAAI Conference on Artificial Intelligence (AAAI'11)}, year = {2011}, urlN = {aaaiSA11.pdf}, abstract={We present a computational method to generate explanations to answers of complex queries over biomedical ontologies and databases, using the high-level representation and efficient automated reasoners of Answer Set Programming. We show the applicability of our approach with some queries related to drug discovery over PHARMGKB, DRUGBANK, BIOGRID, CTD and SIDER.} }

We present a computational method to generate explanations to answers of complex queries over biomedical ontologies and databases, using the high-level representation and efficient automated reasoners of Answer Set Programming. We show the applicability of our approach with some queries related to drug discovery over PHARMGKB, DRUGBANK, BIOGRID, CTD and SIDER.

Finding Answers and Generating Explanations for Complex Biomedical Queries.
Erdem, E.; Erdem, Y.; Erdogan, H.; and Oztok, U.
In

N bibtex abstract 1 download

*Proc. of the 25th AAAI Conference on Artificial Intelligence (AAAI'11)*, 2011.N bibtex abstract 1 download

@inproceedings{aaai11, author = {Esra Erdem and Yelda Erdem and Halit Erdogan and Umut Oztok}, title = {Finding Answers and Generating Explanations for Complex Biomedical Queries}, booktitle = {Proc. of the 25th AAAI Conference on Artificial Intelligence (AAAI'11)}, year = {2011}, urlN = {aaai11.pdf}, abstract={We present new methods to efficiently answer complex queries over biomedical ontologies and databases considering the relevant parts of these knowledge resources, and to generate shortest explanations to justify these answers. Both algorithms rely on the high-level representation and efficient solvers of Answer Set Programming. We apply these algorithms to find answers and explanations to some complex queries related to drug discovery, over PHARMGKB, DRUGBANK, BIOGRID, CTD and SIDER.} }

We present new methods to efficiently answer complex queries over biomedical ontologies and databases considering the relevant parts of these knowledge resources, and to generate shortest explanations to justify these answers. Both algorithms rely on the high-level representation and efficient solvers of Answer Set Programming. We apply these algorithms to find answers and explanations to some complex queries related to drug discovery, over PHARMGKB, DRUGBANK, BIOGRID, CTD and SIDER.

Causal Reasoning for Planning and Coordination of Multiple Housekeeping Robots.
Aker, E.; Erdogan, A.; Erdem, E.; and Patoglu, V.
In

N bibtex abstract 1 download

*Proc. of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'11)*, 2011.N bibtex abstract 1 download

@inproceedings{lpnmr11, author = {E. Aker and A. Erdogan and E. Erdem and V. Patoglu}, title = {Causal Reasoning for Planning and Coordination of Multiple Housekeeping Robots}, booktitle = {Proc. of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'11)}, year = {2011}, urlN = {lpnmr11.pdf}, abstract={We consider a housekeeping domain with multiple cleaning robots and represent it in the action language C+. With such a formalization of the domain, a plan can be computed using the causal reasoner CCALC for each robot to tidy some part of the house. However, to find a plan that characterizes a feasible trajectory that does not collide with obstacles, we need to consider geometric reasoning as well. For that, we embed motion planning in the domain description using external predicates. For safe execution of feasible plans, we introduce a planning and monitoring algorithm so that the robots can recover from plan execution failures due to heavy objects that cannot be lifted alone. The coordination of robots to help each other is considered for such a recovery. We illustrate the applicability of this algorithm with a simulation of a housekeeping domain. }}

We consider a housekeeping domain with multiple cleaning robots and represent it in the action language C+. With such a formalization of the domain, a plan can be computed using the causal reasoner CCALC for each robot to tidy some part of the house. However, to find a plan that characterizes a feasible trajectory that does not collide with obstacles, we need to consider geometric reasoning as well. For that, we embed motion planning in the domain description using external predicates. For safe execution of feasible plans, we introduce a planning and monitoring algorithm so that the robots can recover from plan execution failures due to heavy objects that cannot be lifted alone. The coordination of robots to help each other is considered for such a recovery. We illustrate the applicability of this algorithm with a simulation of a housekeeping domain.

Applications of Answer Set Programming in Phylogenetic Systematics.
Erdem, E.
In

Link N bibtex abstract buy 2 downloads

*Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning: Essays in Honor of Michael Gelfond*, pages 415-431. 2011.Link N bibtex abstract buy 2 downloads

@incollection{erdem11, author={Esra Erdem}, title={Applications of Answer Set Programming in Phylogenetic Systematics}, booktitle={Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning: Essays in Honor of Michael Gelfond}, pages={415-431}, year={2011}, ee={http://www.springerlink.com/content/978-3-642-20831-7/#section=888988&page=1&locus=0}, urlN={mg65.pdf}, abstract={We summarize some applications of Answer Set Programming (ASP) in phylogenetics systematics, focusing on the challenges, how they are handled using computational methods of ASP, the usefulness of the ASP-based methods/tools both from the point of view of phylogenetic systematics and from the point of view of ASP.} }

We summarize some applications of Answer Set Programming (ASP) in phylogenetics systematics, focusing on the challenges, how they are handled using computational methods of ASP, the usefulness of the ASP-based methods/tools both from the point of view of phylogenetic systematics and from the point of view of ASP.

Housekeeping with Multiple Autonomous Robots: Representation, Reasoning and Execution.
Aker, E.; Erdogan, A.; Erdem, E.; and Patoglu, V.
In

N bibtex abstract

*Proc. of the Tenth International Symposium on Logical Formalization on Commonsense Reasoning (Commonsense 2011)*, 2011.N bibtex abstract

@inproceedings{cs11, author = {E. Aker and A. Erdogan and E. Erdem and V. Patoglu}, title = {Housekeeping with Multiple Autonomous Robots: Representation, Reasoning and Execution}, booktitle = {Proc. of the Tenth International Symposium on Logical Formalization on Commonsense Reasoning (Commonsense 2011)}, year = {2011}, urlN = {cs11.pdf}, abstract={We formalize actions and change in a housekeeping domain with multiple cleaning robots, and commonsense knowledge about this domain, in the action language C+. Geometric reasoning is lifted to high-level representation by embedding motion planning in the domain description using external predicates. With such a formalization of the domain, a plan can be computed using the causal reasoner CCALC for each robot to tidy some part of the house. We introduce a planning and monitoring algorithm for safe execution of these plans, so that it can recover from plan failures due to collision with movable objects whose presence and location are not known in advance or due to heavy objects that cannot be lifted alone. We illustrate the applicability of this algorithm with a simulation of a housekeeping domain. }}

We formalize actions and change in a housekeeping domain with multiple cleaning robots, and commonsense knowledge about this domain, in the action language C+. Geometric reasoning is lifted to high-level representation by embedding motion planning in the domain description using external predicates. With such a formalization of the domain, a plan can be computed using the causal reasoner CCALC for each robot to tidy some part of the house. We introduce a planning and monitoring algorithm for safe execution of these plans, so that it can recover from plan failures due to collision with movable objects whose presence and location are not known in advance or due to heavy objects that cannot be lifted alone. We illustrate the applicability of this algorithm with a simulation of a housekeeping domain.

Combining High-Level Causal Reasoning with Low-Level Geometric Reasoning and Motion Planning for Robotic Manipulation.
Erdem, E.; Haspalamutgil, K.; Palaz, C.; Patoglu, V.; and Uras, T.
In

N bibtex abstract 4 downloads

*Proc. of the 2011 IEEE International Conference on Robotics and Automation (ICRA 2011)*, 2011.N bibtex abstract 4 downloads

@inproceedings{icra11, author = {E. Erdem and K. Haspalamutgil and C. Palaz and V. Patoglu and T. Uras}, title = {Combining High-Level Causal Reasoning with Low-Level Geometric Reasoning and Motion Planning for Robotic Manipulation}, booktitle = {Proc. of the 2011 IEEE International Conference on Robotics and Automation (ICRA 2011)}, year = {2011}, urlN = {icra2011.pdf}, abstract={We present a formal framework that combines high-level representation and causality-based reasoning with low-level geometric reasoning and motion planning. The framework features bilateral interaction between task and motion planning, and embeds geometric reasoning in causal reasoning, thanks to several advantages inherited from its underlying components. In particular, our choice of using a causality-based high-level formalism for describing action domains allows us to represent ramifications and state/transition constraints, and embed in such formal domain descriptions externally defined functions implemented in some programming language (e.g., C++). Moreover, given such a domain description, the causal reasoner based on this formalism (i.e., the Causal Calculator) allows us to compute optimal solutions (e.g., shortest plans) for elaborate planning/prediction problems with temporal constraints. Utilizing these features of high-level representation and reasoning, we can combine causal reasoning, motion planning and geometric planning to find feasible kinematic solutions to task-level problems. In our framework, the causal reasoner guides the motion planner by finding an optimal task-plan; if there is no feasible kinematic solution for that task-plan then the motion planner guides the causal reasoner by modifying the planning problem with new temporal constraints. Furthermore, while computing a task-plan, the causal reasoner takes into account geometric models and kinematic relations by means of external predicates implemented for geometric reasoning (e.g., to check some collisions); in that sense the geometric reasoner guides the causal reasoner to find feasible kinematic solutions. We illustrate an application of this framework to robotic manipulation, with two pantograph robots on a complex assembly task that requires concurrent execution of actions. } }

We present a formal framework that combines high-level representation and causality-based reasoning with low-level geometric reasoning and motion planning. The framework features bilateral interaction between task and motion planning, and embeds geometric reasoning in causal reasoning, thanks to several advantages inherited from its underlying components. In particular, our choice of using a causality-based high-level formalism for describing action domains allows us to represent ramifications and state/transition constraints, and embed in such formal domain descriptions externally defined functions implemented in some programming language (e.g., C++). Moreover, given such a domain description, the causal reasoner based on this formalism (i.e., the Causal Calculator) allows us to compute optimal solutions (e.g., shortest plans) for elaborate planning/prediction problems with temporal constraints. Utilizing these features of high-level representation and reasoning, we can combine causal reasoning, motion planning and geometric planning to find feasible kinematic solutions to task-level problems. In our framework, the causal reasoner guides the motion planner by finding an optimal task-plan; if there is no feasible kinematic solution for that task-plan then the motion planner guides the causal reasoner by modifying the planning problem with new temporal constraints. Furthermore, while computing a task-plan, the causal reasoner takes into account geometric models and kinematic relations by means of external predicates implemented for geometric reasoning (e.g., to check some collisions); in that sense the geometric reasoner guides the causal reasoner to find feasible kinematic solutions. We illustrate an application of this framework to robotic manipulation, with two pantograph robots on a complex assembly task that requires concurrent execution of actions.

2010
(13)

Querying Biomedical Ontologies in Natural Language using Answer Set Programming.
Erdogan, H.; Oztok, U.; Erdem, Y.; and Erdem, E.
In

N bibtex abstract

*Proc. of the Third International Workshop on Semantic Web Applications and Tools for Life Sciences (SWAT4LS'10)*, 2010.N bibtex abstract

@inproceedings{swat4ls10, author = {Halit Erdogan and Umut Oztok and Yelda Erdem and Esra Erdem}, title = {Querying Biomedical Ontologies in Natural Language using Answer Set Programming}, booktitle = {Proc. of the Third International Workshop on Semantic Web Applications and Tools for Life Sciences (SWAT4LS'10)}, year = {2010}, urlN = {swat4ls10.pdf}, abstract={We present a formal framework to find answers and explanations to complex queries over biomedical ontologies and databases, using the high-level representation and efficient automated reasoners of Answer Set Programming. Over this framework, we develop an intelligent user-interface that allows users to enter biomedical queries in a natural language, and that presents the answers also in that natural language. We show the applicability of our approach with some queries over PharmGKB, DrugBank, CTD and Sider.} }

We present a formal framework to find answers and explanations to complex queries over biomedical ontologies and databases, using the high-level representation and efficient automated reasoners of Answer Set Programming. Over this framework, we develop an intelligent user-interface that allows users to enter biomedical queries in a natural language, and that presents the answers also in that natural language. We show the applicability of our approach with some queries over PharmGKB, DrugBank, CTD and Sider.

Updating action domain descriptions.
Eiter, T.; Erdem, E.; Fink, M.; and Senko, J.

Link N bibtex abstract

*Artificial Intelligence*, 174(15): 1172-1221. 2010.Link N bibtex abstract

@article{EiterEFS10, author = {Thomas Eiter and Esra Erdem and Michael Fink and J{\'a}n Senko}, title = {Updating action domain descriptions}, journal = {Artificial Intelligence}, volume = {174}, number = {15}, year = {2010}, pages = {1172-1221}, ee = {http://dx.doi.org/10.1016/j.artint.2010.07.004}, urlN = {http://people.sabanciuniv.edu/esraerdem/papers/aij10.pdf}, abstract = {Incorporating new information into a knowledge base is an important problem which has been widely investigated. In this paper, we study this problem in a formal framework for reasoning about actions and change. In this framework, action domains are described in an action language whose semantics is based on the notion of causality. Unlike the formalisms considered in the related work, this language allows straightforward representation of non-deterministic effects and indirect effects of (possibly concurrent) actions, as well as state constraints; therefore, the updates can be more general than elementary statements. The expressivity of this formalism allows us to study the update of an action domain description with a more general approach compared to related work. First of all, we consider the update of an action description with respect to further criteria, for instance, by ensuring that the updated description entails some observations, assertions, or general domain properties that constitute further constraints that are not expressible in an action description in general. Moreover, our framework allows us to discriminate amongst alternative updates of action domain descriptions and to single out a most preferable one, based on a given preference relation possibly dependent on the specified criteria. We study semantic and computational aspects of the update problem, and establish basic properties of updates as well as a decomposition theorem that gives rise to a divide and conquer approach to updating action descriptions under certain conditions. Furthermore, we study the computational complexity of decision problems around computing solutions, both for the generic setting and for two particular preference relations, viz. set-inclusion and weight-based preference. While deciding the existence of solutions and recognizing solutions are PSPACE-complete problems in general, the problems fall back into the polynomial hierarchy under restrictions on the additional constraints. We finally discuss methods to compute solutions and approximate solutions (which disregard preference). Our results provide a semantic and computational basis for developing systems that incorporate new information into action domain descriptions in an action language, in the presence of additional constraints. }, }

Incorporating new information into a knowledge base is an important problem which has been widely investigated. In this paper, we study this problem in a formal framework for reasoning about actions and change. In this framework, action domains are described in an action language whose semantics is based on the notion of causality. Unlike the formalisms considered in the related work, this language allows straightforward representation of non-deterministic effects and indirect effects of (possibly concurrent) actions, as well as state constraints; therefore, the updates can be more general than elementary statements. The expressivity of this formalism allows us to study the update of an action domain description with a more general approach compared to related work. First of all, we consider the update of an action description with respect to further criteria, for instance, by ensuring that the updated description entails some observations, assertions, or general domain properties that constitute further constraints that are not expressible in an action description in general. Moreover, our framework allows us to discriminate amongst alternative updates of action domain descriptions and to single out a most preferable one, based on a given preference relation possibly dependent on the specified criteria. We study semantic and computational aspects of the update problem, and establish basic properties of updates as well as a decomposition theorem that gives rise to a divide and conquer approach to updating action descriptions under certain conditions. Furthermore, we study the computational complexity of decision problems around computing solutions, both for the generic setting and for two particular preference relations, viz. set-inclusion and weight-based preference. While deciding the existence of solutions and recognizing solutions are PSPACE-complete problems in general, the problems fall back into the polynomial hierarchy under restrictions on the additional constraints. We finally discuss methods to compute solutions and approximate solutions (which disregard preference). Our results provide a semantic and computational basis for developing systems that incorporate new information into action domain descriptions in an action language, in the presence of additional constraints.

A Tight Integration of Task Planning and Motion Planning in an Execution Monitoring Framework.
Haspalamutgil, K.; Palaz, C.; Uras, T.; Erdem, E.; and Patoglu, V.
In

N bibtex abstract 3 downloads

*Proc. of AAAI'10 Workshop, Bridging The Gap Between Task And Motion Planning (BTAMP'10)*, 2010.N bibtex abstract 3 downloads

@inproceedings{btamp10, author = {K. Haspalamutgil and C. Palaz and T. Uras and E. Erdem and V. Patoglu}, title = {A Tight Integration of Task Planning and Motion Planning in an Execution Monitoring Framework}, booktitle = {Proc. of AAAI'10 Workshop, Bridging The Gap Between Task And Motion Planning (BTAMP'10)}, year = {2010}, urlN = {btamp10.pdf}, abstract={We study integration of task planning and motion planning in a general execution monitoring framework. We show the applicability of this framework, on a modified version of Tower of Hanoi where the orientations of rings matter and rotations of rings maybe required while being moved. We represent this problem as a planning problem in the action language C+, and compute a shortest task plan using the reasoning system CCALC. A collision-free trajectory for the task plan (if one exists) is computed by a motion planning algorithm, using Rapidly exploring Random Trees. The monitoring agent invokes replanning upon two kinds of failures: when a continuous trajectory for a task plan cannot be computed, and when the execution of the plan fails due to external intervention. We demonstrate the effectiveness of our approach by implementing it using two robotic manipulators on a physical experimental setup.} }

We study integration of task planning and motion planning in a general execution monitoring framework. We show the applicability of this framework, on a modified version of Tower of Hanoi where the orientations of rings matter and rotations of rings maybe required while being moved. We represent this problem as a planning problem in the action language C+, and compute a shortest task plan using the reasoning system CCALC. A collision-free trajectory for the task plan (if one exists) is computed by a motion planning algorithm, using Rapidly exploring Random Trees. The monitoring agent invokes replanning upon two kinds of failures: when a continuous trajectory for a task plan cannot be computed, and when the execution of the plan fails due to external intervention. We demonstrate the effectiveness of our approach by implementing it using two robotic manipulators on a physical experimental setup.

Bilissel Montaj Planlama ve Icra Takibi.
Haspalamutgil, K.; Palaz, C.; Uras, T.; Erdem, E.; and Patoglu, V.
In

N bibtex

*Proc. of the National Conference on Automatic Control (TOK'10)*, 2010. In TurkishN bibtex

@inproceedings{tok10, author = {K. Haspalamutgil and C. Palaz and T. Uras and E. Erdem and V. Patoglu}, title = {Bilissel Montaj Planlama ve Icra Takibi}, booktitle = {Proc. of the National Conference on Automatic Control (TOK'10)}, year = {2010}, urlN = {tok10.pdf}, note = {In Turkish}, }

Exploiting UMLS Semantics for Checking Semantic Consistency among UMLS concepts.
Erdogan, H.; Erdem, E.; and Bodenreider, O.
In

N bibtex abstract 1 download

*Proc. of the 13th International Congress on Medical Informatics (MedInfo'10)*, 2010.N bibtex abstract 1 download

@inproceedings{medinfo10, author = {Halit Erdogan and Esra Erdem and Olivier Bodenreider}, booktitle = {Proc. of the 13th International Congress on Medical Informatics (MedInfo'10)}, year = {2010}, title = {Exploiting {UMLS} Semantics for Checking Semantic Consistency among {UMLS} concepts}, urlN = {2009-medinfo-he.pdf}, abstract = {To quantify semantic inconsistency in UMLS concepts from the perspective of their hierarchical relations and to show through examples how semantically-inconsistent concepts can help reveal erroneous synonymy relations. Methods: Inconsistency is defined in reference to concepts from the UMLS Metathesaurus. Consistency is evaluated by comparing the semantic groups of the two concepts in each pair of hierarchically-related concepts. A limited number of inconsistent concepts was inspected manually. Results: 81,512 concepts are inconsistent due to the differences in semantic groups between a concept and its parent. Four examples of wrong synonymy are presented. Conclusions: A vast majority of incon-sistent hierarchical relations are not indicative of any errors. We discovered an interesting semantic pattern along hierarchies, which seems associated with wrong synonymy.}, }

To quantify semantic inconsistency in UMLS concepts from the perspective of their hierarchical relations and to show through examples how semantically-inconsistent concepts can help reveal erroneous synonymy relations. Methods: Inconsistency is defined in reference to concepts from the UMLS Metathesaurus. Consistency is evaluated by comparing the semantic groups of the two concepts in each pair of hierarchically-related concepts. A limited number of inconsistent concepts was inspected manually. Results: 81,512 concepts are inconsistent due to the differences in semantic groups between a concept and its parent. Four examples of wrong synonymy are presented. Conclusions: A vast majority of incon-sistent hierarchical relations are not indicative of any errors. We discovered an interesting semantic pattern along hierarchies, which seems associated with wrong synonymy.

Using amino acid typing to improve the accuracy of NMR structure based assignments.
Halit Erdogan, undefined; and Apaydin, M. S.
In

bibtex abstract

*Proc. of the 5th International Symposium on Health Informatics and Bioinformatics (HIBIT'10)*, 2010.bibtex abstract

@inproceedings{hibit10, author = {Halit Erdogan, and Mehmet Serkan Apaydin}, booktitle = {Proc. of the 5th International Symposium on Health Informatics and Bioinformatics (HIBIT'10)}, title = {Using amino acid typing to improve the accuracy of NMR structure based assignments}, year = {2010}, abstract = {Nuclear Magnetic Resonance (NMR) spectroscopy is an important experimental technique that allows one to study protein structure in solution. An important challenge in NMR protein structure determination is the assignment of NMR peaks to corresponding nuclei. In structure-based assignment (SBA), the aim is to perform the assignments with the help of a homologous protein. NVR-BIP is a tool that uses Nuclear Vector Replacement’s (NVR) scoring function and binary integer programming to solve SBA problem. In this work, we introduce a method to improve NVR-BIP’s assignment accuracy with amino acid typing. We use CRAACK that takes the chemical shifts of C, N and H atoms and returns the possible amino acids along with their confidence scores. We obtain improved assignment accuracies and our results show the effectiveness of integrating amino acid typing with NVR.} }

Nuclear Magnetic Resonance (NMR) spectroscopy is an important experimental technique that allows one to study protein structure in solution. An important challenge in NMR protein structure determination is the assignment of NMR peaks to corresponding nuclei. In structure-based assignment (SBA), the aim is to perform the assignments with the help of a homologous protein. NVR-BIP is a tool that uses Nuclear Vector Replacement’s (NVR) scoring function and binary integer programming to solve SBA problem. In this work, we introduce a method to improve NVR-BIP’s assignment accuracy with amino acid typing. We use CRAACK that takes the chemical shifts of C, N and H atoms and returns the possible amino acids along with their confidence scores. We obtain improved assignment accuracies and our results show the effectiveness of integrating amino acid typing with NVR.

Quantifying solutions in answer set programming.
Erdogan, H.
In

N bibtex abstract

*Proc. of the 1st Computer Science Student Workshop (CSW'10)*, 2010.N bibtex abstract

@inproceedings{csw10, author = {Halit Erdogan}, booktitle = {Proc. of the 1st Computer Science Student Workshop (CSW'10)}, title = {Quantifying solutions in answer set programming}, year = {2010}, abstract = {Answer Set Programming (ASP) is a declarative programming paradigm oriented towards solving NP-hard problems. Due to the expressive representation language and efficient solvers, ASP can be useful for a wide-range of knowledgeintensive applications from different fields. In ASP, the idea is to provide a declarative representation of the problem as an ASP program whose models (called answer sets) correspond to solutions. Since many problems have numerous solutions, instead of computing all solutions, it is sometimes desirable to compute a subset of preferred solutions. With this motivation, we present novel methods to quantify answer sets in ASP for extracting preferred solutions only. We show the effectiveness of these methods on real world applications.}, urlN = {csw10-halit.pdf}, }

Answer Set Programming (ASP) is a declarative programming paradigm oriented towards solving NP-hard problems. Due to the expressive representation language and efficient solvers, ASP can be useful for a wide-range of knowledgeintensive applications from different fields. In ASP, the idea is to provide a declarative representation of the problem as an ASP program whose models (called answer sets) correspond to solutions. Since many problems have numerous solutions, instead of computing all solutions, it is sometimes desirable to compute a subset of preferred solutions. With this motivation, we present novel methods to quantify answer sets in ASP for extracting preferred solutions only. We show the effectiveness of these methods on real world applications.

Genome Rearrangement and Planning: Revisited.
Uras, T.; and Erdem, E.
In

N bibtex abstract

*Proc. of the 20th International Conference on Automated Planning and Scheduling (ICAPS'10)*, 2010.N bibtex abstract

@inproceedings{uraserd10, author = {Tansel Uras and Esra Erdem}, title = {Genome Rearrangement and Planning: Revisited}, booktitle = {Proc. of the 20th International Conference on Automated Planning and Scheduling (ICAPS'10)}, year = {2010}, urlN = {icaps10.pdf}, abstract = {Evolutionary trees of species can be reconstructed by pairwise comparison of their entire genomes. Such a comparison can be quantified by determining the number of events that change the order of genes in a genome. Earlier Erdem and Tillier formulated the pairwise comparison of entire genomes as the problem of planning rearrangement events that transform one genome to the other. We reformulate this problem as a planning problem to extend its applicability to genomes with multiple copies of genes and with unequal gene content, and illustrate its applicability and effectiveness on three real datasets: mitochondrial genomes of Metazoa, chloroplast genomes of Campanulaceae, chloroplast genomes of various land plants and green algae.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

Evolutionary trees of species can be reconstructed by pairwise comparison of their entire genomes. Such a comparison can be quantified by determining the number of events that change the order of genes in a genome. Earlier Erdem and Tillier formulated the pairwise comparison of entire genomes as the problem of planning rearrangement events that transform one genome to the other. We reformulate this problem as a planning problem to extend its applicability to genomes with multiple copies of genes and with unequal gene content, and illustrate its applicability and effectiveness on three real datasets: mitochondrial genomes of Metazoa, chloroplast genomes of Campanulaceae, chloroplast genomes of various land plants and green algae.

Genome rearrangement: A Planning approach.
Uras, T.
In

N bibtex

*Proc. of the 1st Computer Science Student Workshop (CSW'10)*, 2010.N bibtex

@inproceedings{csw10-tansel, author = {Tansel Uras}, booktitle = {Proc. of the 1st Computer Science Student Workshop (CSW'10)}, title = {Genome rearrangement: A Planning approach}, year = {2010}, urlN = {csw10-tansel.pdf}, }

Haplotype Inference with Polyallelic and Polyploid Genotypes.
Erdem, O.
In

N bibtex

*Proc. of the 1st Computer Science Student Workshop (CSW'10)*, 2010.N bibtex

@inproceedings{csw10-ozan, author = {Ozan Erdem}, booktitle = {Proc. of the 1st Computer Science Student Workshop (CSW'10)}, title = {Haplotype Inference with Polyallelic and Polyploid Genotypes}, year = {2010}, urlN = {csw10-ozan.pdf}, }

Finding Semantic Inconsistencies in UMLS using Answer Set Programming.
Erdogan, H.; Bodenreider, O.; and Erdem, E.
In

Link N bibtex abstract

*Proc. of the 24th AAAI Conference on Artificial Intelligence (AAAI'10)*, 2010.Link N bibtex abstract

@inproceedings{sa10-halit, author = {Halit Erdogan and Olivier Bodenreider and Esra Erdem}, booktitle = {Proc. of the 24th AAAI Conference on Artificial Intelligence (AAAI'10)}, title = {Finding Semantic Inconsistencies in UMLS using Answer Set Programming}, year = {2010}, ee = {http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1655/2296}, urlN = {sa10-halit.pdf}, abstract = {We introduce a new method to find semantic inconsistencies (i.e., concepts with erroneous synonymity) in the Unified Medical Language System (UMLS). The idea is to identify the inconsistencies by comparing the semantic groups of hierarchically-related concepts using Answer Set Programming. With this method, we identified several inconsistent concepts in UMLS and discovered an interesting semantic pattern along hierarchies, which seems associated with wrong synonymy.}, }

We introduce a new method to find semantic inconsistencies (i.e., concepts with erroneous synonymity) in the Unified Medical Language System (UMLS). The idea is to identify the inconsistencies by comparing the semantic groups of hierarchically-related concepts using Answer Set Programming. With this method, we identified several inconsistent concepts in UMLS and discovered an interesting semantic pattern along hierarchies, which seems associated with wrong synonymy.

Genome Rearrangement: A Planning Approach.
Uras, T.; and Erdem, E.
In

Link N bibtex abstract

*Proc. of the 24th AAAI Conference on Artificial Intelligence (AAAI'10)*, 2010.Link N bibtex abstract

@inproceedings{sa10-tansel, author = {Tansel Uras and Esra Erdem}, booktitle = {Proc. of the 24th AAAI Conference on Artificial Intelligence (AAAI'10)}, title = {Genome Rearrangement: A Planning Approach}, year = {2010}, ee = {http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1664/2324}, urlN = {sa10-tansel.pdf}, abstract = {Evolutionary trees of species can be reconstructed by pairwise comparison of their entire genomes. Such a comparison can be quantified by determining the number of events that change the order of genes in a genome. Earlier Erdem and Tillier formulated the pairwise comparison of entire genomes as the problem of planning rearrangement events that transform one genome to the other. We reformulate this problem as a planning problem to extend its applicability to genomes with multiple copies of genes and with unequal gene content, and illustrate its applicability and effectiveness on three real datasets: mitochondrial genomes of Metazoa, chloroplast genomes of Campanulaceae, chloroplast genomes of various land plants and green algae.}, }

Evolutionary trees of species can be reconstructed by pairwise comparison of their entire genomes. Such a comparison can be quantified by determining the number of events that change the order of genes in a genome. Earlier Erdem and Tillier formulated the pairwise comparison of entire genomes as the problem of planning rearrangement events that transform one genome to the other. We reformulate this problem as a planning problem to extend its applicability to genomes with multiple copies of genes and with unequal gene content, and illustrate its applicability and effectiveness on three real datasets: mitochondrial genomes of Metazoa, chloroplast genomes of Campanulaceae, chloroplast genomes of various land plants and green algae.

Computing Weighted Solutions in ASP: Representation-Based Method vs. Search-Based Method.
Cakmak, D.; Erdem, E.; and Erdogan, H.
In

Link N bibtex abstract

*Proc. of the 17th International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA'10)*, 2010.Link N bibtex abstract

@inproceedings{rcra10, ee = {http://ceur-ws.org/Vol-616/}, urln = {rcra10.pdf}, author = {Duygu Cakmak and Esra Erdem and Halit Erdogan}, booktitle = {Proc. of the 17th International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA'10)}, abstract = {For some problems with many solutions, like planning and phylogeny reconstruction, one way to compute more desirable solutions is to assign weights to solutions, and then pick the ones whose weights are over (resp. below) a threshold. This paper studies computing weighted solutions to such problems in Answer Set Programming. We investigate two sorts of methods for computing weighted solutions: one suggests modifying the representation of the problem and the other suggests modifying the search procedure of the answer set solver. We show the applicability and the effectiveness of these methods in reconstructing weighted phylogenies for Indo-European languages. We also compare these methods in terms of computational efficiency; the experimental results show that the search-based method is better.}, year = {2010}, title = {Computing Weighted Solutions in ASP: Representation-Based Method vs. Search-Based Method}, }

For some problems with many solutions, like planning and phylogeny reconstruction, one way to compute more desirable solutions is to assign weights to solutions, and then pick the ones whose weights are over (resp. below) a threshold. This paper studies computing weighted solutions to such problems in Answer Set Programming. We investigate two sorts of methods for computing weighted solutions: one suggests modifying the representation of the problem and the other suggests modifying the search procedure of the answer set solver. We show the applicability and the effectiveness of these methods in reconstructing weighted phylogenies for Indo-European languages. We also compare these methods in terms of computational efficiency; the experimental results show that the search-based method is better.

2009
(10)

Transforming controlled natural language biomedical queries into answer set programs.
Erdem, E.; and Yeniterzi, R.
In

N bibtex abstract

*Proc. of the Workshop on BioNLP (BioNLP'09)*, pages 117-124, 2009.N bibtex abstract

@inproceedings{1572381, author = {Erdem, Esra and Yeniterzi, Reyyan}, title = {Transforming controlled natural language biomedical queries into answer set programs}, booktitle = {Proc. of the Workshop on BioNLP (BioNLP'09)}, year = {2009}, pages = {117-124}, urlN = {W09-1315.pdf}, abstract = {We introduce a controlled natural language for biomedical queries, called BIOQUERYCNL, and present an algorithm to convert a biomedical query in this language into a program in answer set programming (ASP) --- a formal framework to automate reasoning about knowledge. BIOQUERYCNL allows users to express complex queries (possibly containing nested relative clauses and cardinality constraints) over biomedical ontologies; and such a transformation of BIOQUERYCNL queries into ASP programs is useful for automating reasoning about biomedical ontologies by means of ASP solvers. We precisely describe the grammar of BIOQUERYCNL, implement our transformation algorithm, and illustrate its applicability to biomedical queries by some examples.}, }

We introduce a controlled natural language for biomedical queries, called BIOQUERYCNL, and present an algorithm to convert a biomedical query in this language into a program in answer set programming (ASP) --- a formal framework to automate reasoning about knowledge. BIOQUERYCNL allows users to express complex queries (possibly containing nested relative clauses and cardinality constraints) over biomedical ontologies; and such a transformation of BIOQUERYCNL queries into ASP programs is useful for automating reasoning about biomedical ontologies by means of ASP solvers. We precisely describe the grammar of BIOQUERYCNL, implement our transformation algorithm, and illustrate its applicability to biomedical queries by some examples.

10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009, Potsdam, Germany, September 14-18, 2009. Proceedings.
Erdem, E.; Lin, F.; and Schaub, T.
, editor
s.
Volume 5753, of Lecture Notes in Computer Science. 2009.Springer.

Link bibtex buy

Link bibtex buy

@proceedings{DBLP:conf/lpnmr/2009, editor = {Esra Erdem and Fangzhen Lin and Torsten Schaub}, title = {10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009, Potsdam, Germany, September 14-18, 2009. Proceedings}, booktitle = {LPNMR}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {5753}, year = {2009}, isbn = {978-3-642-04237-9}, ee = {http://dx.doi.org/10.1007/978-3-642-04238-6}, bibsource = {DBLP, http://dblp.uni-trier.de}, }

Finding Similar or Diverse Solutions in Answer Set Programming.
Eiter, T.; Erdem, E.; Erdogan, H.; and Fink, M.
In

Link N bibtex abstract

*Proc. of the 25th International Conference of Logic Programming (ICLP'09)*, pages 342-356, 2009.Link N bibtex abstract

@inproceedings{DBLP:conf/iclp/EiterEEF09, author = {Thomas Eiter and Esra Erdem and Halit Erdogan and Michael Fink}, title = {Finding Similar or Diverse Solutions in Answer Set Programming}, booktitle = {Proc. of the 25th International Conference of Logic Programming (ICLP'09)}, year = {2009}, pages = {342-356}, ee = {http://dx.doi.org/10.1007/978-3-642-02846-5_29}, bibsource = {DBLP, http://dblp.uni-trier.de}, urlN = {iclp09.pdf}, abstract = {We study finding similar or diverse solutions of a given computational problem, in answer set programming, and introduce offline methods and online methods to compute them using answer set solvers.We analyze the computational complexity of some problems that are related to finding similar or diverse solutions, and show the applicability and effectiveness of our methods in phylogeny reconstruction.}, }

We study finding similar or diverse solutions of a given computational problem, in answer set programming, and introduce offline methods and online methods to compute them using answer set solvers.We analyze the computational complexity of some problems that are related to finding similar or diverse solutions, and show the applicability and effectiveness of our methods in phylogeny reconstruction.

Bridging the Gap between High-Level Reasoning and Low-Level Control.
Caldiran, O.; Haspalamutgil, K.; Ok, A.; Palaz, C.; Erdem, E.; and Patoglu, V.
In

Link N bibtex abstract

*Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09)*, pages 342-354, 2009.Link N bibtex abstract

@inproceedings{DBLP:conf/lpnmr/CaldiranHOPEP09, author = {Ozan Caldiran and Kadir Haspalamutgil and Abdullah Ok and Can Palaz and Esra Erdem and Volkan Patoglu}, title = {Bridging the Gap between High-Level Reasoning and Low-Level Control}, booktitle = {Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09)}, year = {2009}, pages = {342-354}, ee = {http://dx.doi.org/10.1007/978-3-642-04238-6_29}, urlN = {lpnmr09-cogrobo.pdf}, abstract = {We present a formal framework where the action description language C+ is used to provide multiple robots with high-level reasoning in the style of cognitive robotics. We show the applicability of this framework on two LEGO MINDSTORMS NXT robots, in an action domain that involves concurrent execution of actions by multiple agents.}, }

We present a formal framework where the action description language C+ is used to provide multiple robots with high-level reasoning in the style of cognitive robotics. We show the applicability of this framework on two LEGO MINDSTORMS NXT robots, in an action domain that involves concurrent execution of actions by multiple agents.

Computing Weighted Solutions in Answer Set Programming.
Cakmak, D.; Erdem, E.; and Erdogan, H.
In

Link N bibtex abstract 1 download

*Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09)*, pages 416-422, 2009.Link N bibtex abstract 1 download

@inproceedings{DBLP:conf/lpnmr/CakmakEE09, author = {Duygu Cakmak and Esra Erdem and Halit Erdogan}, title = {Computing Weighted Solutions in Answer Set Programming}, booktitle = {Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09)}, year = {2009}, pages = {416-422}, ee = {http://dx.doi.org/10.1007/978-3-642-04238-6_36}, bibsource = {DBLP, http://dblp.uni-trier.de}, urlN = {lpnmr09-wasp.pdf}, abstract = {For some problems with many solutions, like planning and phylogeny reconstruction, one way to compute more desirable solutions is to assign weights to solutions, and then pick the ones whose weights are over (resp. below) a threshold. This paper studies computing weighted solutions to such problems in Answer Set Programming. We investigate two sorts of methods for computing weighted solutions: one suggests modifying the representation of the problem and the other suggests modifying the search procedure of the answer set solver. We show the applicability and the effectiveness of these methods in phylogeny reconstruction.}, }

For some problems with many solutions, like planning and phylogeny reconstruction, one way to compute more desirable solutions is to assign weights to solutions, and then pick the ones whose weights are over (resp. below) a threshold. This paper studies computing weighted solutions to such problems in Answer Set Programming. We investigate two sorts of methods for computing weighted solutions: one suggests modifying the representation of the problem and the other suggests modifying the search procedure of the answer set solver. We show the applicability and the effectiveness of these methods in phylogeny reconstruction.

PHYLO-ASP: Phylogenetic Systematics with Answer Set Programming.
Erdem, E.
In

Link N bibtex abstract

*Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09)*, pages 567-572, 2009.Link N bibtex abstract

@inproceedings{DBLP:conf/lpnmr/Erdem09, author = {Esra Erdem}, title = {PHYLO-ASP: Phylogenetic Systematics with Answer Set Programming}, booktitle = {Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09)}, year = {2009}, pages = {567-572}, ee = {http://dx.doi.org/10.1007/978-3-642-04238-6_59}, bibsource = {DBLP, http://dblp.uni-trier.de}, urlN = {lpnmr09-phylo.pdf}, abstract = {This note summarizes the use of Answer Set Programming to solve various computational problems to infer phylogenetic trees and phylogenetic networks, and discusses its applicability and effectiveness on some real taxa.}, }

This note summarizes the use of Answer Set Programming to solve various computational problems to infer phylogenetic trees and phylogenetic networks, and discusses its applicability and effectiveness on some real taxa.

HAPLO-ASP: Haplotype Inference Using Answer Set Programming.
Erdem, E.; Erdem, O.; and Türe, F.
In

Link N bibtex abstract

*Proc. of the 10th International Conference of Logic Programming and Nonmonotonic Reasoning (LPNMR'09)*, pages 573-578, 2009.Link N bibtex abstract

@inproceedings{DBLP:conf/lpnmr/ErdemET09, author = {Esra Erdem and Ozan Erdem and Ferhan T{\"u}re}, title = {HAPLO-ASP: Haplotype Inference Using Answer Set Programming}, booktitle = {Proc. of the 10th International Conference of Logic Programming and Nonmonotonic Reasoning (LPNMR'09)}, year = {2009}, pages = {573-578}, ee = {http://dx.doi.org/10.1007/978-3-642-04238-6_60}, bibsource = {DBLP, http://dblp.uni-trier.de}, urlN = {lpnmr09-haplo.pdf}, abstract = {Identifying maternal and paternal inheritance is essential to be able to find the set of genes responsible for a particular disease. However, due to technological limitations, we have access to genotype data (genetic makeup of an individual), and determining haplotypes (genetic makeup of the parents) experimentally is a costly and time consuming procedure. With these biological motivations, we study haplotype inference -- determining the haplotypes that form a given set of genotypes -- using Answer Set Programming; we call our approach HAPLO-ASP. This note summarizes the range of problems that can be handled by HAPLO-ASP, and its applicability and effectiveness on real data in comparison with the other existing approaches.}, }

Identifying maternal and paternal inheritance is essential to be able to find the set of genes responsible for a particular disease. However, due to technological limitations, we have access to genotype data (genetic makeup of an individual), and determining haplotypes (genetic makeup of the parents) experimentally is a costly and time consuming procedure. With these biological motivations, we study haplotype inference -- determining the haplotypes that form a given set of genotypes -- using Answer Set Programming; we call our approach HAPLO-ASP. This note summarizes the range of problems that can be handled by HAPLO-ASP, and its applicability and effectiveness on real data in comparison with the other existing approaches.

From Discrete Task Plans to Continuous Trajectories.
Caldiran, O.; Haspalamutgil, K.; Ok, A.; Palaz, C.; Erdem, E.; and Patoglu, V.
In

N bibtex abstract

*Proc. of the 19th International Conference on Automated Planning and Scheduling (ICAPS'09) Workshop, Bridging The Gap Between Task And Motion Planning*, 2009.N bibtex abstract

@inproceedings{bridge, author = {O. Caldiran and K. Haspalamutgil and A. Ok and C. Palaz and E. Erdem and V. Patoglu}, title = {From Discrete Task Plans to Continuous Trajectories}, booktitle = {Proc. of the 19th International Conference on Automated Planning and Scheduling (ICAPS'09) Workshop, Bridging The Gap Between Task And Motion Planning}, year = {2009}, urlN = {btamp09.pdf}, abstract = {We present a logic-based framework to provide robots with high-level reasoning, such as planning. This framework uses the action description language C+ to represent actions and changes, and the system CCALC to reason about them. In particular, we can represent action domains that involve concurrent actions and additive fluents; based on this description, we can compute shortest plans to a planning problem that involves cost constraints. We show the applicability of this framework on two LEGO MINDSTORMS NXT robots: we compute a discrete task plan (possibly with concurrency) with a cost less than a specified value, and transform this plan into a continuous collision-free trajectory.}, }

We present a logic-based framework to provide robots with high-level reasoning, such as planning. This framework uses the action description language C+ to represent actions and changes, and the system CCALC to reason about them. In particular, we can represent action domains that involve concurrent actions and additive fluents; based on this description, we can compute shortest plans to a planning problem that involves cost constraints. We show the applicability of this framework on two LEGO MINDSTORMS NXT robots: we compute a discrete task plan (possibly with concurrency) with a cost less than a specified value, and transform this plan into a continuous collision-free trajectory.

Robot Kontrolu icin Mantiksal Akil Yurutme.
Caldiran, O.; Haspalamutgil, K.; Ok, A.; Palaz, C.; Erdem, E.; and Patoglu, V.
In

N bibtex

*Proc. of the National Conference on Automatic Control (TOK'09)*, 2009. In TurkishN bibtex

@inproceedings{akilyurut, author = {O. Caldiran and K. Haspalamutgil and A. Ok and C. Palaz and E. Erdem and V. Patoglu}, title = {Robot Kontrolu icin Mantiksal Akil Yurutme}, booktitle = {Proc. of the National Conference on Automatic Control (TOK'09)}, year = {2009}, urlN = {tok09.pdf}, note = {In Turkish}, }

Comparing ASP and CP on four grid puzzles.
Celik, M.; Erdogan, H.; Tahaoglu, F.; Uras, T.; and Erdem, E.
In

N Paper bibtex abstract 2 downloads

*Proc. of the 16th International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA'09)*, 2009.N Paper bibtex abstract 2 downloads

@inproceedings{rcra09, urln = {rcra09.pdf}, author = {Mehmet Celik and Halit Erdogan and Firat Tahaoglu and Tansel Uras and Esra Erdem}, url = {http://krr.sabanciuniv.edu/projects/gridpuzzle/}, booktitle = {Proc. of the 16th International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA'09)}, title = {Comparing ASP and CP on four grid puzzles}, year = {2009}, abstract = {We study two declarative programming languages namely Answer Set Programming (ASP) and Constraint Programming (CP) on four grid puzzles: Akari, Kakuro, Nurikabe, and Heyawake. We represent these problems in both formalisms in a systematic way and compute their solutions using ASP system Clasp and CP system Comet. We compare the ASP approach with the CP approach both from the point of view of knowledge representation and from the point of view of computational time and memory.} }

We study two declarative programming languages namely Answer Set Programming (ASP) and Constraint Programming (CP) on four grid puzzles: Akari, Kakuro, Nurikabe, and Heyawake. We represent these problems in both formalisms in a systematic way and compute their solutions using ASP system Clasp and CP system Comet. We compare the ASP approach with the CP approach both from the point of view of knowledge representation and from the point of view of computational time and memory.

2008
(5)

Efficient Haplotype Inference with Answer Set Programming.
Türe, F.; and Erdem, E.
In

N bibtex abstract

*Proc. of the 23rd AAAI Conference on Artificial Intelligence (AAAI'08)*, pages 1834-1835, 2008. Student abstractN bibtex abstract

@inproceedings{DBLP:conf/aaai/TureE08, author = {Ferhan T{\"u}re and Esra Erdem}, title = {Efficient Haplotype Inference with Answer Set Programming}, booktitle = {Proc. of the 23rd AAAI Conference on Artificial Intelligence (AAAI'08)}, year = {2008}, pages = {1834-1835}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {Identifying maternal and paternal inheritance is essential to be able to ﬁnd the set of genes responsible for a particular disease. Although we have access to genotype data (genetic makeup of an individual), determining haplotypes (genetic makeup of the parents) experimentally is a costly and time consuming procedure due to technological limitations. With these biological motivations, we study a computational prob- lem, called Haplotype Inference with Pure Parsimony (HIPP), that asks for the minimal number of haplotypes that form a given set of genotypes. We introduce a novel approach to solving HIPP, using Answer Set Programming (ASP). Ac- cording to our experiments with a large number of problem instances (some automatically generated and some real), our ASP-based approach solves the most number of problems compared to other approaches based on, e.g., integer linear programming, branch and bound algorithms, SAT-based al- gorithms, or pseudo-boolean optimization methods.}, urlN = {sa08.pdf}, note = {Student abstract}, }

Identifying maternal and paternal inheritance is essential to be able to ﬁnd the set of genes responsible for a particular disease. Although we have access to genotype data (genetic makeup of an individual), determining haplotypes (genetic makeup of the parents) experimentally is a costly and time consuming procedure due to technological limitations. With these biological motivations, we study a computational prob- lem, called Haplotype Inference with Pure Parsimony (HIPP), that asks for the minimal number of haplotypes that form a given set of genotypes. We introduce a novel approach to solving HIPP, using Answer Set Programming (ASP). Ac- cording to our experiments with a large number of problem instances (some automatically generated and some real), our ASP-based approach solves the most number of problems compared to other approaches based on, e.g., integer linear programming, branch and bound algorithms, SAT-based al- gorithms, or pseudo-boolean optimization methods.

Efficient Haplotype Inference with Answer Set Programming.
Erdem, E.; and Türe, F.
In

N bibtex abstract

*Proc. of the 23rd AAAI Conference on Artificial Intelligence (AAAI'08)*, pages 436-441, 2008.N bibtex abstract

@inproceedings{DBLP:conf/aaai/ErdemT08, author = {Esra Erdem and Ferhan T{\"u}re}, title = {Efficient Haplotype Inference with Answer Set Programming}, booktitle = {Proc. of the 23rd AAAI Conference on Artificial Intelligence (AAAI'08)}, year = {2008}, pages = {436-441}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {Identifying maternal and paternal inheritance is essential to be able to find the set of genes responsible for a particular disease. However, due to technological limitations, we have access to genotype data (genetic makeup of an individual), and determining haplotypes (genetic makeup of the parents) experimentally is a costly and time consuming procedure. With these biological motivations, we study a computational problem, called Haplotype Inference by Pure Parsimony (HIPP), that asks for the minimal number of haplotypes that form a given set of genotypes. HIPP has been studied using integer linear programming, branch and bound algorithms, SAT-based algorithms, or pseudo-boolean optimization methods. We introduce a new approach to solving HIPP, using Answer Set Programming (ASP). According to our experiments with a large number of problem instances (some automatically generated and some real), our ASP-based approach solves the most number of problems compared with other approaches. Due to the expressivity of the knowledge representation language of ASP, our approach allows us to solve variations of HIPP, e.g., with additional domain specific information, such as patterns/parts of haplotypes observed for some gene family, or with some missing genotype information. In this sense, the ASP-based approach is more general than the existing approaches to haplotype inference.}, urlN = {aaai08.pdf}, }

Identifying maternal and paternal inheritance is essential to be able to find the set of genes responsible for a particular disease. However, due to technological limitations, we have access to genotype data (genetic makeup of an individual), and determining haplotypes (genetic makeup of the parents) experimentally is a costly and time consuming procedure. With these biological motivations, we study a computational problem, called Haplotype Inference by Pure Parsimony (HIPP), that asks for the minimal number of haplotypes that form a given set of genotypes. HIPP has been studied using integer linear programming, branch and bound algorithms, SAT-based algorithms, or pseudo-boolean optimization methods. We introduce a new approach to solving HIPP, using Answer Set Programming (ASP). According to our experiments with a large number of problem instances (some automatically generated and some real), our ASP-based approach solves the most number of problems compared with other approaches. Due to the expressivity of the knowledge representation language of ASP, our approach allows us to solve variations of HIPP, e.g., with additional domain specific information, such as patterns/parts of haplotypes observed for some gene family, or with some missing genotype information. In this sense, the ASP-based approach is more general than the existing approaches to haplotype inference.

Undoing the effects of action sequences.
Eiter, T.; Erdem, E.; and Faber, W.

Link bibtex abstract

*Applied Logic*, 6(3): 380-415. 2008.Link bibtex abstract

@article{DBLP:journals/japll/EiterEF08, author = {Thomas Eiter and Esra Erdem and Wolfgang Faber}, title = {Undoing the effects of action sequences}, journal = {Applied Logic}, volume = {6}, number = {3}, year = {2008}, pages = {380-415}, ee = {http://dx.doi.org/10.1016/j.jal.2007.05.002}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {In this paper, we study the following basic problem: After having executed a sequence of actions, find a sequence of actions that brings the agent back to the state just before this execution. It emerges, for example, if an agent needs to find out which action sequences are undoable, and which ones are committed choices. A prototypical scenario is in the context of plan execution in a nondeterministic environment: Upon detecting that after executing some steps of the plan, an unintended state has been reached, backtracking to an earlier state by taking appropriate undo actions can be useful for recovery. In this paper, we consider the problem of undoing the effects of an action sequence by means of a reverse plan. Intuitively, by executing a reverse plan for an action sequence AS at the state S' reached after AS, the agent can always reach the state S she was at just before executing AS, possibly subject to conditions on the current state and S. Notably, this problem is different from a vanilla planning problem, since the state we have to get back to is in general unknown. We study this problem in a general logic-based action representation framework that can accommodate nondeterminism and concurrency. We formally define the notion of a reverse plan and determine the computational complexity of the existence and the recognition of such a plan. Guided by these results, we then present algorithms for constructing reverse plans. Unsurprisingly, the problem is intractable in general, and we present a knowledge compilation approach that constructs offline a reverse plan library for efficient (in some cases, linear time) online computation of action reversals. Our results for the generic framework can be adapted for expressive action languages such as C+ or K.}, }

In this paper, we study the following basic problem: After having executed a sequence of actions, find a sequence of actions that brings the agent back to the state just before this execution. It emerges, for example, if an agent needs to find out which action sequences are undoable, and which ones are committed choices. A prototypical scenario is in the context of plan execution in a nondeterministic environment: Upon detecting that after executing some steps of the plan, an unintended state has been reached, backtracking to an earlier state by taking appropriate undo actions can be useful for recovery. In this paper, we consider the problem of undoing the effects of an action sequence by means of a reverse plan. Intuitively, by executing a reverse plan for an action sequence AS at the state S' reached after AS, the agent can always reach the state S she was at just before executing AS, possibly subject to conditions on the current state and S. Notably, this problem is different from a vanilla planning problem, since the state we have to get back to is in general unknown. We study this problem in a general logic-based action representation framework that can accommodate nondeterminism and concurrency. We formally define the notion of a reverse plan and determine the computational complexity of the existence and the recognition of such a plan. Guided by these results, we then present algorithms for constructing reverse plans. Unsurprisingly, the problem is intractable in general, and we present a knowledge compilation approach that constructs offline a reverse plan library for efficient (in some cases, linear time) online computation of action reversals. Our results for the generic framework can be adapted for expressive action languages such as C+ or K.

Comparing ASP, CP, ILP on two Challenging Applications: Wire Routing and Haplotype Inference.
Coban, E.; Erdem, E.; and Ture, F.
In

N bibtex abstract

*Proc. of the 2nd International Workshop on Logic and Search (LaSh 2008)*, 2008.N bibtex abstract

@INPROCEEDINGS{comparing, author = {Elvin Coban and Esra Erdem and Ferhan Ture}, title = {Comparing {ASP}, {CP}, {ILP} on two Challenging Applications: Wire Routing and Haplotype Inference}, year = {2008}, booktitle = {Proc. of the 2nd International Workshop on Logic and Search (LaSh 2008)}, abstract = {We study three declarative programming paradigms, Answer Set Programming (ASP), Constraint Programming (CP), and Integer Linear Programming (ILP), on two challenging applications: wire routing and haplotype inference. We represent these problems in each formalism in a systematic way, compare the formulations both from the point of view of knowledge representation (e.g., how tolerant they are to elaborations) and from the point of view of computational efficiency (in terms of computation time and program size). We discuss possible ways of improving the computational efficiency, and other reformulations of the problems based on different mathematical models.}, urlN = {lash08.pdf}, }

We study three declarative programming paradigms, Answer Set Programming (ASP), Constraint Programming (CP), and Integer Linear Programming (ILP), on two challenging applications: wire routing and haplotype inference. We represent these problems in each formalism in a systematic way, compare the formulations both from the point of view of knowledge representation (e.g., how tolerant they are to elaborations) and from the point of view of computational efficiency (in terms of computation time and program size). We discuss possible ways of improving the computational efficiency, and other reformulations of the problems based on different mathematical models.

A Preliminary Report on Answering Complex Queries related to Drug Discovery using Answer Set Programming.
Bodenreider, O.; Coban, Z. H.; Doganay, M. C.; and Erdem, E.
In

N bibtex abstract

*Proc. of the 3rd International Workshop on Applications of Logic Programming to the Semantic Web and Web Services (ALPSWS'08)*, 2008.N bibtex abstract

@INPROCEEDINGS{Bodenreider_apreliminary, author = {Olivier Bodenreider and Zeynep H. Coban and Mahir C. Doganay and Esra Erdem}, title = {A Preliminary Report on Answering Complex Queries related to Drug Discovery using Answer Set Programming}, year = {2008}, booktitle = {Proc. of the 3rd International Workshop on Applications of Logic Programming to the Semantic Web and Web Services (ALPSWS'08)}, urlN = {alpsws.pdf}, abstract = {We introduce a new method for integrating relevant parts of knowledge extracted from biomedical ontologies and answering complex queries related to drug safety and discovery, using Semantic Web technologies and answer set programming. The applicability of this method is illustrated in detail on some parts of existing biomedical ontologies. Its effectiveness is demonstrated by computing an answer to a real-world biomedical query that requires the integration of NCBI Entrez Gene and the Gene Ontology.}, }

We introduce a new method for integrating relevant parts of knowledge extracted from biomedical ontologies and answering complex queries related to drug safety and discovery, using Semantic Web technologies and answer set programming. The applicability of this method is illustrated in detail on some parts of existing biomedical ontologies. Its effectiveness is demonstrated by computing an answer to a real-world biomedical query that requires the integration of NCBI Entrez Gene and the Gene Ontology.

2007
(6)

Forgetting Actions in Domain Descriptions.
Erdem, E.; and Ferraris, P.
In

N bibtex abstract

*Proc. of the 22nd AAAI Conference on Artificial Intelligence (AAAI'07)*, pages 409-414, 2007.N bibtex abstract

@inproceedings{DBLP:conf/aaai/ErdemF07, author = {Esra Erdem and Paolo Ferraris}, title = {Forgetting Actions in Domain Descriptions}, booktitle = {Proc. of the 22nd AAAI Conference on Artificial Intelligence (AAAI'07)}, year = {2007}, pages = {409-414}, bibsource = {DBLP, http://dblp.uni-trier.de}, urlN = {aaai07.pdf}, abstract = {Forgetting irrelevant/problematic actions in a domain description can be useful in solving reasoning problems, such as query answering, planning, conflict resolution, prediction, postdiction, etc.. Motivated by such applications, we study what forgetting is, how forgetting can be done, and for which applications forgetting can be useful and how, in the context of reasoning about actions. We study these questions in the action language {\cal C} (a formalism based on causal explanations), and relate it to forgetting in classical logic and logic programming. }, }

Forgetting irrelevant/problematic actions in a domain description can be useful in solving reasoning problems, such as query answering, planning, conflict resolution, prediction, postdiction, etc.. Motivated by such applications, we study what forgetting is, how forgetting can be done, and for which applications forgetting can be useful and how, in the context of reasoning about actions. We study these questions in the action language a̧l C (a formalism based on causal explanations), and relate it to forgetting in classical logic and logic programming.

On Reversing Actions: Algorithms and Complexity.
Eiter, T.; Erdem, E.; and Faber, W.
In

Link bibtex abstract

*Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI'07)*, pages 336-341, 2007.Link bibtex abstract

@inproceedings{DBLP:conf/ijcai/EiterEF07, author = {Thomas Eiter and Esra Erdem and Wolfgang Faber}, title = {On Reversing Actions: Algorithms and Complexity}, booktitle = {Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI'07)}, year = {2007}, pages = {336-341}, ee = {http://dli.iiit.ac.in/ijcai/IJCAI-2007/PDF/IJCAI07-052.pdf}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {Reversing actions is the following problem: After executing a sequence of actions, which sequence of actions brings the agent back to the state just before this execution (an action reversal). Notably, this problem is different from a vanilla planning problem since the state we have to get back to is in general unknown. It emerges, for example, if an agent needs to find out which action sequences are undoable, and which ones are committed choices. It has applications related to plan execution and monitoring in nondeterministic domains, such as recovering from a failed execution by partially undoing the plan, dynamically switching from one executed plan to another, or restarting plans. We formalize action reversal in a logic-based action framework and characterize its computational complexity. Since unsurprisingly, the problem is intractable in general, we present a knowledge compilation approach that constructs offline a reverse plan library for efficient (in some cases, linear time) online computation of action reversals. Our results for the generic framework can be easily applied for expressive action languages such as {\cal C}+ or {\cal K}. }, }

Reversing actions is the following problem: After executing a sequence of actions, which sequence of actions brings the agent back to the state just before this execution (an action reversal). Notably, this problem is different from a vanilla planning problem since the state we have to get back to is in general unknown. It emerges, for example, if an agent needs to find out which action sequences are undoable, and which ones are committed choices. It has applications related to plan execution and monitoring in nondeterministic domains, such as recovering from a failed execution by partially undoing the plan, dynamically switching from one executed plan to another, or restarting plans. We formalize action reversal in a logic-based action framework and characterize its computational complexity. Since unsurprisingly, the problem is intractable in general, we present a knowledge compilation approach that constructs offline a reverse plan library for efficient (in some cases, linear time) online computation of action reversals. Our results for the generic framework can be easily applied for expressive action languages such as a̧l C+ or a̧l K.

Comparing action descriptions based on semantic preferences.
Eiter, T.; Erdem, E.; Fink, M.; and Senko, J.

Link bibtex abstract

*Annals of Mathematics and Artificial Intelligence*, 50(3-4): 273-304. 2007.Link bibtex abstract

@article{DBLP:journals/amai/EiterEFS07, author = {Thomas Eiter and Esra Erdem and Michael Fink and J{\'a}n Senko}, title = {Comparing action descriptions based on semantic preferences}, journal = {Annals of Mathematics and Artificial Intelligence}, volume = {50}, number = {3-4}, year = {2007}, pages = {273-304}, ee = {http://dx.doi.org/10.1007/s10472-007-9077-y}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {The focus of this paper is on action domain descriptions whose meaning can be represented by transition diagrams. We introduce several semantic measures to compare such action descriptions, based on preferences over possible states of the world and preferences over some given conditions (observations, assertions, etc.) about the domain, as well as the probabilities of possible transitions. This preference information is used to assemble a weight which is assigned to an action description. As applications of this approach, we study updating action descriptions and identifying elaboration tolerant action descriptions, with respect to some given conditions. With a semantic approach based on preferences, not only, for some problems, we get more plausible solutions, but also, for some problems without any solutions due to too strong conditions, we can identify which conditions to relax to obtain a solution. We further study computational issues, and give a characterization of the computational complexity of computing the semantic measures. }, }

The focus of this paper is on action domain descriptions whose meaning can be represented by transition diagrams. We introduce several semantic measures to compare such action descriptions, based on preferences over possible states of the world and preferences over some given conditions (observations, assertions, etc.) about the domain, as well as the probabilities of possible transitions. This preference information is used to assemble a weight which is assigned to an action description. As applications of this approach, we study updating action descriptions and identifying elaboration tolerant action descriptions, with respect to some given conditions. With a semantic approach based on preferences, not only, for some problems, we get more plausible solutions, but also, for some problems without any solutions due to too strong conditions, we can identify which conditions to relax to obtain a solution. We further study computational issues, and give a characterization of the computational complexity of computing the semantic measures.

A Logic-Based Approach to Finding Explanations for Discrepancies in Optimistic Plan Execution.
Eiter, T.; Erdem, E.; Faber, W.; and Senko, J.

Link bibtex abstract

*Fundamenta Informaticae*, 79(1-2): 25-69. 2007.Link bibtex abstract

@article{DBLP:journals/fuin/EiterEFS07, author = {Thomas Eiter and Esra Erdem and Wolfgang Faber and J{\'a}n Senko}, title = {A Logic-Based Approach to Finding Explanations for Discrepancies in Optimistic Plan Execution}, journal = {Fundamenta Informaticae}, volume = {79}, number = {1-2}, year = {2007}, pages = {25-69}, ee = {http://iospress.metapress.com/openurl.asp?genre=article{\&}issn=0169-2968{\&}volume=79{\&}issue=1{\&}spage=25}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {Consider an agent executing a plan with nondeterministic actions, in a dynamic environment, which might fail. Suppose that she is given a description of this action domain, including specifications of effects of actions, and a set of trajectories for the execution of this plan, where each trajectory specifies a possible execution of the plan in this domain. After executing some part of the plan, suppose that she obtains information about the current state of the world, and notices that she is not at a correct state relative to the given trajectories. How can she find an explanation (a point of failure) for such a discrepancy? An answer to this question can be useful for different purposes. In the context of execution monitoring, points of failure can determine some checkpoints that specify when to check for discrepancies, and they can sometimes be used for recovering from discrepancies that cause plan failures. At the modeling level, points of failure may provide useful insight into the action domain for a better understanding of the domain, or reveal errors in the formalization of the domain. We study the question above in a general logic-based knowledge representation framework, which can accommodate nondeterminism and concurrency. In this framework, we define a discrepancy and an explanation for it, and analyze the computational complexity of detecting discrepancies and finding explanations for them. We introduce a method for computing explanations, and report about a realization of this method using DLVK, which is a logic-programming based system for reasoning about actions and change. }, }

Consider an agent executing a plan with nondeterministic actions, in a dynamic environment, which might fail. Suppose that she is given a description of this action domain, including specifications of effects of actions, and a set of trajectories for the execution of this plan, where each trajectory specifies a possible execution of the plan in this domain. After executing some part of the plan, suppose that she obtains information about the current state of the world, and notices that she is not at a correct state relative to the given trajectories. How can she find an explanation (a point of failure) for such a discrepancy? An answer to this question can be useful for different purposes. In the context of execution monitoring, points of failure can determine some checkpoints that specify when to check for discrepancies, and they can sometimes be used for recovering from discrepancies that cause plan failures. At the modeling level, points of failure may provide useful insight into the action domain for a better understanding of the domain, or reveal errors in the formalization of the domain. We study the question above in a general logic-based knowledge representation framework, which can accommodate nondeterminism and concurrency. In this framework, we define a discrepancy and an explanation for it, and analyze the computational complexity of detecting discrepancies and finding explanations for them. We introduce a method for computing explanations, and report about a realization of this method using DLVK, which is a logic-programming based system for reasoning about actions and change.

Inferring Phylogenetic Trees Using Answer Set Programming.
Brooks, D. R.; Erdem, E.; Erdogan, S. T.; Minett, J. W.; and Ringe, D.

Link bibtex abstract 2 downloads

*Automated Reasoning*, 39(4): 471-511. 2007.Link bibtex abstract 2 downloads

@article{DBLP:journals/jar/BrooksEEMR07, author = {Daniel R. Brooks and Esra Erdem and Selim T. Erdogan and James W. Minett and Donald Ringe}, title = {Inferring Phylogenetic Trees Using Answer Set Programming}, journal = {Automated Reasoning}, volume = {39}, number = {4}, year = {2007}, pages = {471-511}, ee = {http://dx.doi.org/10.1007/s10817-007-9082-1}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {We describe the reconstruction of a phylogeny for a set of taxa, with a character-based cladistics approach, in a declarative knowledge representation formalism, and show how to use computational methods of answer set programming to generate conjectures about the evolution of the given taxa. We have applied this computational method in two domains: to historical analysis of languages, and to historical analysis of parasite-host systems. In particular, using this method, we have computed some plausible phylogenies for Chinese dialects, for Indo-European language groups, and for Alcataenia species. Some of these plausible phylogenies are different from the ones computed by other software. Using this method, we can easily describe domain specific information (e.g., temporal and geographical constraints), and thus prevent the reconstruction of some phylogenies that are not plausible. }, }

We describe the reconstruction of a phylogeny for a set of taxa, with a character-based cladistics approach, in a declarative knowledge representation formalism, and show how to use computational methods of answer set programming to generate conjectures about the evolution of the given taxa. We have applied this computational method in two domains: to historical analysis of languages, and to historical analysis of parasite-host systems. In particular, using this method, we have computed some plausible phylogenies for Chinese dialects, for Indo-European language groups, and for Alcataenia species. Some of these plausible phylogenies are different from the ones computed by other software. Using this method, we can easily describe domain specific information (e.g., temporal and geographical constraints), and thus prevent the reconstruction of some phylogenies that are not plausible.

Solving Challenging Grid Puzzles with Answer Set Programming.
Cayli, M.; Karatop, A. G.; Kavlak, E.; Kaynar, H.; Ture, F.; and Erdem, E.
In

N bibtex abstract

*Proc. of ASP*, pages 175-190, 2007.N bibtex abstract

@INPROCEEDINGS{grid, author = {Merve Cayli and Ayse Gül Karatop and Emrah Kavlak and Hakan Kaynar and Ferhan Ture and Esra Erdem}, title = {Solving Challenging Grid Puzzles with Answer Set Programming}, year = {2007}, booktitle = {Proc. of ASP}, pages = {175-190}, abstract = {We study four challenging grid puzzles, Nurikabe, Heyawake, Masyu, Bag Puzzle, interesting for answer set programming (ASP) from the viewpoints of representation and computation: they show expressivity of ASP, they are good examples of a representation methodology, and they form a useful suite of benchmarks for evaluating/improving computational methods for nontight programs.}, urlN = {puzzles-final.pdf}, }

We study four challenging grid puzzles, Nurikabe, Heyawake, Masyu, Bag Puzzle, interesting for answer set programming (ASP) from the viewpoints of representation and computation: they show expressivity of ASP, they are good examples of a representation methodology, and they form a useful suite of benchmarks for evaluating/improving computational methods for nontight programs.

2006
(4)

Resolving Conflicts in Action Descriptions.
Eiter, T.; Erdem, E.; Fink, M.; and Senko, J.
In

N bibtex abstract

*ECAI 2006, 17th European Conference on Artificial Intelligence, August 29 - September 1, 2006, Riva del Garda, Italy, Including Prestigious Applications of Intelligent Systems (PAIS 2006), Proceedings*, pages 367-371, 2006.N bibtex abstract

@inproceedings{DBLP:conf/ecai/EiterEFS06, author = {Thomas Eiter and Esra Erdem and Michael Fink and J{\'a}n Senko}, title = {Resolving Conflicts in Action Descriptions}, booktitle = {ECAI 2006, 17th European Conference on Artificial Intelligence, August 29 - September 1, 2006, Riva del Garda, Italy, Including Prestigious Applications of Intelligent Systems (PAIS 2006), Proceedings}, year = {2006}, pages = {367-371}, urlN = {debug-ecai06-final.pdf}, abstract = {We study resolving conflicts between an action description and a set of conditions (possibly obtained from observations), in the context of action languages. In this formal framework, the meaning of an action description can be represented by a transition diagram, a directed graph whose nodes correspond to states and whose edges correspond to transitions describing action occurrences. This allows us to characterize conflicts by means of states and transitions of the given action description that violate some given conditions. We introduce a basic method to resolve such conflicts by modifying the action description, and discuss how the user can be supported in obtaining more preferred solutions. For that, we identify helpful questions the user may ask (e.g., which specific parts of the action description cause a conflict with some given condition), and we provide answers to them using properties of action descriptions and transition diagrams. Finally, we discuss the computational complexity of these questions in terms of related decision problems.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

We study resolving conflicts between an action description and a set of conditions (possibly obtained from observations), in the context of action languages. In this formal framework, the meaning of an action description can be represented by a transition diagram, a directed graph whose nodes correspond to states and whose edges correspond to transitions describing action occurrences. This allows us to characterize conflicts by means of states and transitions of the given action description that violate some given conditions. We introduce a basic method to resolve such conflicts by modifying the action description, and discuss how the user can be supported in obtaining more preferred solutions. For that, we identify helpful questions the user may ask (e.g., which specific parts of the action description cause a conflict with some given condition), and we provide answers to them using properties of action descriptions and transition diagrams. Finally, we discuss the computational complexity of these questions in terms of related decision problems.

Comparing Action Descriptions Based on Semantic Preferences.
Eiter, T.; Erdem, E.; Fink, M.; and Senko, J.
In

Link bibtex abstract

*Logics in Artificial Intelligence, 10th European Conference, JELIA 2006, Liverpool, UK, September 13-15, 2006, Proceedings*, pages 124-137, 2006.Link bibtex abstract

@inproceedings{DBLP:conf/jelia/EiterEFS06, author = {Thomas Eiter and Esra Erdem and Michael Fink and J{\'a}n Senko}, title = {Comparing Action Descriptions Based on Semantic Preferences}, booktitle = {Logics in Artificial Intelligence, 10th European Conference, JELIA 2006, Liverpool, UK, September 13-15, 2006, Proceedings}, year = {2006}, pages = {124-137}, ee = {http://dx.doi.org/10.1007/11853886_12}, abstract = {We consider action domain descriptions whose meaning can be represented by transition diagrams. We introduce several semantic measures to compare such action descriptions, based on preferences over possible states of the world and preferences over some given conditions (observations, assertions, etc.) about the domain, as well as the probabilities of possible transitions. This preference information is used to assemble a weight which is assigned to an action description. As an application of this approach, we study the problem of updating action descriptions with respect to some given conditions. With a semantic approach based on preferences, not only, for some problems, we get more plausible solutions, but also, for some problems without any solutions due to too strong conditions, we can identify which conditions to relax to obtain a solution. We conclude with computational issues, and characterize the complexity of computing the semantic measures.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

We consider action domain descriptions whose meaning can be represented by transition diagrams. We introduce several semantic measures to compare such action descriptions, based on preferences over possible states of the world and preferences over some given conditions (observations, assertions, etc.) about the domain, as well as the probabilities of possible transitions. This preference information is used to assemble a weight which is assigned to an action description. As an application of this approach, we study the problem of updating action descriptions with respect to some given conditions. With a semantic approach based on preferences, not only, for some problems, we get more plausible solutions, but also, for some problems without any solutions due to too strong conditions, we can identify which conditions to relax to obtain a solution. We conclude with computational issues, and characterize the complexity of computing the semantic measures.

Representing Action Domains with Numeric-Valued Fluents.
Erdem, E.; and Gabaldon, A.
In

Link bibtex abstract

*Logics in Artificial Intelligence, 10th European Conference, JELIA 2006, Liverpool, UK, September 13-15, 2006, Proceedings*, pages 151-163, 2006.Link bibtex abstract

@inproceedings{DBLP:conf/jelia/ErdemG06, author = {Esra Erdem and Alfredo Gabaldon}, title = {Representing Action Domains with Numeric-Valued Fluents}, booktitle = {Logics in Artificial Intelligence, 10th European Conference, JELIA 2006, Liverpool, UK, September 13-15, 2006, Proceedings}, year = {2006}, pages = {151-163}, ee = {http://dx.doi.org/10.1007/11853886_14}, abstract = {We present a general method to formalize action domains with numeric-valued fluents whose values are incremented or decremented by executions of actions, and show how it can be applied to the action description language C+ and to the concurrent situation calculus. This method can handle nonserializable concurrent actions, as well as ramifications on numeric-valued fluents, which are described in terms of some new causal structures, called contribution rules.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

We present a general method to formalize action domains with numeric-valued fluents whose values are incremented or decremented by executions of actions, and show how it can be applied to the action description language C+ and to the concurrent situation calculus. This method can handle nonserializable concurrent actions, as well as ramifications on numeric-valued fluents, which are described in terms of some new causal structures, called contribution rules.

Temporal phylogenetic networks and logic programming.
Erdem, E.; Lifschitz, V.; and Ringe, D.

Link bibtex abstract

*TPLP*, 6(5): 539-558. 2006.Link bibtex abstract

@article{DBLP:journals/tplp/ErdemLR06, author = {Esra Erdem and Vladimir Lifschitz and Donald Ringe}, title = {Temporal phylogenetic networks and logic programming}, journal = {TPLP}, volume = {6}, number = {5}, year = {2006}, pages = {539-558}, ee = {http://dx.doi.org/10.1017/S1471068406002729}, abstract = {The concept of a temporal phylogenetic network is a mathematical model of evolution of a family of natural languages. It takes into account the fact that languages can trade their characteristics with each other when linguistic communities are in contact, and also that a contact is only possible when the languages are spoken at the same time. We show how computational methods of answer set programming and constraint logic programming can be used to generate plausible conjectures about contacts between prehistoric linguistic communities, and illustrate our approach by applying it to the evolutionary history of Indo-European languages.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

The concept of a temporal phylogenetic network is a mathematical model of evolution of a family of natural languages. It takes into account the fact that languages can trade their characteristics with each other when linguistic communities are in contact, and also that a contact is only possible when the languages are spoken at the same time. We show how computational methods of answer set programming and constraint logic programming can be used to generate plausible conjectures about contacts between prehistoric linguistic communities, and illustrate our approach by applying it to the evolutionary history of Indo-European languages.

2005
(4)

Genome Rearrangement and Planning.
Erdem, E.; and Tillier, E. R. M.
In

N bibtex abstract

*Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, July 9-13, 2005, Pittsburgh, Pennsylvania, USA*, pages 1139-1144, 2005.N bibtex abstract

@inproceedings{DBLP:conf/aaai/ErdemT05, author = {Esra Erdem and Elisabeth R. M. Tillier}, title = {Genome Rearrangement and Planning}, booktitle = {Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, July 9-13, 2005, Pittsburgh, Pennsylvania, USA}, year = {2005}, pages = {1139-1144}, urlN = {genome.pdf}, abstract = {The genome rearrangement problem is to find the most economical explanation for observed differences between the gene orders of two genomes. Such an explanation is provided in terms of events that change the order of genes in a genome. We present a new approach to the genome rearrangement problem, according to which this problem is viewed as the problem of planning rearrangement events that transform one genome to the other. This method differs from the existing ones in that we can put restrictions on the number of events, specify the cost of events with functions, possibly based on the length of the gene fragment involved, and add constraints controlling search. With this approach, we have described genome rearrangements in the action description language ADL, and studied the evolution of Metazoan mitochondrial genomes and the evolution of Campanulaceae chloroplast genomes using the planner TLplan. We have observed that the phylogenies reconstructed using this approach conform with the most widely accepted ones.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

The genome rearrangement problem is to find the most economical explanation for observed differences between the gene orders of two genomes. Such an explanation is provided in terms of events that change the order of genes in a genome. We present a new approach to the genome rearrangement problem, according to which this problem is viewed as the problem of planning rearrangement events that transform one genome to the other. This method differs from the existing ones in that we can put restrictions on the number of events, specify the cost of events with functions, possibly based on the length of the gene fragment involved, and add constraints controlling search. With this approach, we have described genome rearrangements in the action description language ADL, and studied the evolution of Metazoan mitochondrial genomes and the evolution of Campanulaceae chloroplast genomes using the planner TLplan. We have observed that the phylogenies reconstructed using this approach conform with the most widely accepted ones.

Cumulative Effects of Concurrent Actions on Numeric-Valued Fluents.
Erdem, E.; and Gabaldon, A.
In

N bibtex abstract

*Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, July 9-13, 2005, Pittsburgh, Pennsylvania, USA*, pages 627-632, 2005.N bibtex abstract

@inproceedings{DBLP:conf/aaai/ErdemG05, author = {Esra Erdem and Alfredo Gabaldon}, title = {Cumulative Effects of Concurrent Actions on Numeric-Valued Fluents}, booktitle = {Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, July 9-13, 2005, Pittsburgh, Pennsylvania, USA}, year = {2005}, pages = {627-632}, urlN = {additive-AAAI05.pdf}, abstract = {We propose a situation calculus formalization of action domains that include numeric-valued fluents (so-called additive or measure fluents) and concurrency. Our approach allows formalizing concurrent actions whose effect s increment/decrement the value of additive fluents. For describing indirect effects, we employ mathematical equations in a manner that is inspired by recent work on causality and structural equations.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

We propose a situation calculus formalization of action domains that include numeric-valued fluents (so-called additive or measure fluents) and concurrency. Our approach allows formalizing concurrent actions whose effect s increment/decrement the value of additive fluents. For describing indirect effects, we employ mathematical equations in a manner that is inspired by recent work on causality and structural equations.

Updating Action Domain Descriptions.
Eiter, T.; Erdem, E.; Fink, M.; and Senko, J.
In

Link bibtex abstract

*IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30-August 5, 2005*, pages 418-423, 2005.Link bibtex abstract

@inproceedings{DBLP:conf/ijcai/EiterEFS05, author = {Thomas Eiter and Esra Erdem and Michael Fink and J{\'a}n Senko}, title = {Updating Action Domain Descriptions}, booktitle = {IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30-August 5, 2005}, year = {2005}, pages = {418-423}, ee = {http://www.ijcai.org/papers/1167.pdf}, abstract = {How can an intelligent agent update her knowledge base about an action domain, relative to some conditions (possibly obtained from earlier observations)? We study this question in a formal framework for reasoning about actions and change, in which the meaning of an action domain description can be represented by a directed graph whose nodes correspond to states and whose edges correspond to action occurrences. We define the update of an action domain description in this framework, and show among other results that a solution to this problem can be obtained by a divide-and-conquer approach in some cases. We also introduce methods to compute a solution and an approximate solution to this problem, and analyze the computational complexity of these problems. Finally, we discuss techniques to improve the quality of solutions.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

How can an intelligent agent update her knowledge base about an action domain, relative to some conditions (possibly obtained from earlier observations)? We study this question in a formal framework for reasoning about actions and change, in which the meaning of an action domain description can be represented by a directed graph whose nodes correspond to states and whose edges correspond to action occurrences. We define the update of an action domain description in this framework, and show among other results that a solution to this problem can be obtained by a divide-and-conquer approach in some cases. We also introduce methods to compute a solution and an approximate solution to this problem, and analyze the computational complexity of these problems. Finally, we discuss techniques to improve the quality of solutions.

Character-Based Cladistics and Answer Set Programming.
Brooks, D. R.; Erdem, E.; Minett, J. W.; and Ringe, D.
In

Link bibtex abstract

*Practical Aspects of Declarative Languages, 7th International Symposium, PADL 2005, Long Beach, CA, USA, January 10-11, 2005, Proceedings*, pages 37-51, 2005.Link bibtex abstract

@inproceedings{DBLP:conf/padl/BrooksEMR05, author = {Daniel R. Brooks and Esra Erdem and James W. Minett and Donald Ringe}, title = {Character-Based Cladistics and Answer Set Programming}, booktitle = {Practical Aspects of Declarative Languages, 7th International Symposium, PADL 2005, Long Beach, CA, USA, January 10-11, 2005, Proceedings}, year = {2005}, pages = {37-51}, ee = {http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=3350{\&}spage=37}, abstract = {We describe the reconstruction of a phylogeny for a set of taxa, with a character-based cladistics approach, in a declarative knowledge representation formalism, and show how to use computational methods of answer set programming to generate conjectures about the evolution of the given taxa. We have applied this computational method in two domains: to historical analysis of languages, and to historical analysis of parasite-host systems. In particular, using this method, we have computed some plausible phylogenies for Chinese dialects, for Indo-European language groups, and for Alcataenia species. Some of these plausible phylogenies are different from the ones computed by other software. Using this method, we can easily describe domain specific information (e.g. temporal and geographical constraints), and thus prevent the reconstruction of some phylogenies that are not plausible.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

We describe the reconstruction of a phylogeny for a set of taxa, with a character-based cladistics approach, in a declarative knowledge representation formalism, and show how to use computational methods of answer set programming to generate conjectures about the evolution of the given taxa. We have applied this computational method in two domains: to historical analysis of languages, and to historical analysis of parasite-host systems. In particular, using this method, we have computed some plausible phylogenies for Chinese dialects, for Indo-European language groups, and for Alcataenia species. Some of these plausible phylogenies are different from the ones computed by other software. Using this method, we can easily describe domain specific information (e.g. temporal and geographical constraints), and thus prevent the reconstruction of some phylogenies that are not plausible.

2004
(4)

Diagnosing plan execution discrepancies in a logic-based action framework.
Eiter, T.; Erdem, E.; and Faber, W.
Technical Report INFSYS RR-1843-04-03, Vienna University of Technology, 2004.

Link bibtex abstract

Link bibtex abstract

@techreport{EitErdFab04-2, author = {Thomas Eiter and Esra Erdem and Wolfgang Faber}, title = {Diagnosing plan execution discrepancies in a logic-based action framework}, institution = {Vienna University of Technology}, year = {2004}, number = {INFSYS RR-1843-04-03}, ee = {http://www.kr.tuwien.ac.at/research/reports/rr0403.ps.gz}, abstract = {This paper introduces a logic-based framework for monitoring plan execution relative to a given set of trajectories. According to this framework, a monitoring agent can tell when things go wrong by checking the compatibility of the plan execution with the given trajectories, considering the current state information. She finds an explanation for these detected discrepancies by examining the given trajectories against possible evolutions of the current state from the initial state. Such an explanation provides information about possible points of failure that may be useful in two ways. First, points of failure can be used to determine some checkpoints (specifying when to check for discrepancies), and this may be useful if the plan is executed many times. Second, they can be used for recovering from discrepancies. For instance, the agent can undo the plan execution until a point of failure, from which the remainder of the plan can be (re)executed, thus avoiding an expensive (re)planni ng step. In this paper, we present formal specifications for discrepancies and explanations for them in a general action representation framework, which can accommodate nondeterminism, concurrency, and dynamic worlds. We describe two ways of finding explanations for detected discrepancies, and study their properties. Moreover, we analyze the computational complexity of detecting discrepancies and finding explanations for them, and describe how these computational problems can be solved.} }

This paper introduces a logic-based framework for monitoring plan execution relative to a given set of trajectories. According to this framework, a monitoring agent can tell when things go wrong by checking the compatibility of the plan execution with the given trajectories, considering the current state information. She finds an explanation for these detected discrepancies by examining the given trajectories against possible evolutions of the current state from the initial state. Such an explanation provides information about possible points of failure that may be useful in two ways. First, points of failure can be used to determine some checkpoints (specifying when to check for discrepancies), and this may be useful if the plan is executed many times. Second, they can be used for recovering from discrepancies. For instance, the agent can undo the plan execution until a point of failure, from which the remainder of the plan can be (re)executed, thus avoiding an expensive (re)planni ng step. In this paper, we present formal specifications for discrepancies and explanations for them in a general action representation framework, which can accommodate nondeterminism, concurrency, and dynamic worlds. We describe two ways of finding explanations for detected discrepancies, and study their properties. Moreover, we analyze the computational complexity of detecting discrepancies and finding explanations for them, and describe how these computational problems can be solved.

Undoing the effects of action sequences.
Eiter, T.; Erdem, E.; and Faber, W.
Technical Report INFSYS RR-1843-04-05, Vienna University of Technology, 2004.

Link bibtex abstract

Link bibtex abstract

@techreport{EitErdFab04, author = {Thomas Eiter and Esra Erdem and Wolfgang Faber}, title = {Undoing the effects of action sequences}, institution = {Vienna University of Technology}, year = {2004}, number = {INFSYS RR-1843-04-05}, ee = {http://www.kr.tuwien.ac.at/research/reports/rr0405.ps.gz}, abstract = {When an agent has executed a single action or a sequence of actions, it may sometimes be desirable that the effects of this execution are undone and the agent gets back to the previous state. A prototypical scenario for this is in the context of plan execution in a nondeterministic environment. Upon detecting that after some steps an unintended state has been reached, backtracking by taking appropriate undo actions can be useful for error recovery. In this paper, we thus consider the problem of undoing the effects of an action sequence by means of a reverse plan, in a general logic-based action representation framework that can accommodate nondeterminism and concurrency. Intuitively, by executing a reverse plan for an action sequence ASat the state Sreached after AS, she can always reach the state Sshe was at before executing AS. We formally define the notion of a reverse plan in terms of a logical specification and determine the computational complexity of the major reasoning tasks on it, namely the existence and recognition problem. Guided by these results, we then present algorithms for constructing reverse plans. Since this is intractable in general, we develop a knowledge compilation approach in which a reverse plan library is built offline by finding reverse plans for action sequences, and then a reverse plan for a given action sequence is efficiently constructed online using this library. For the former part, we describe methods based on conformant planning; for the latter, we present a polynomial time algorithm.} }

When an agent has executed a single action or a sequence of actions, it may sometimes be desirable that the effects of this execution are undone and the agent gets back to the previous state. A prototypical scenario for this is in the context of plan execution in a nondeterministic environment. Upon detecting that after some steps an unintended state has been reached, backtracking by taking appropriate undo actions can be useful for error recovery. In this paper, we thus consider the problem of undoing the effects of an action sequence by means of a reverse plan, in a general logic-based action representation framework that can accommodate nondeterminism and concurrency. Intuitively, by executing a reverse plan for an action sequence ASat the state Sreached after AS, she can always reach the state Sshe was at before executing AS. We formally define the notion of a reverse plan in terms of a logical specification and determine the computational complexity of the major reasoning tasks on it, namely the existence and recognition problem. Guided by these results, we then present algorithms for constructing reverse plans. Since this is intractable in general, we develop a knowledge compilation approach in which a reverse plan library is built offline by finding reverse plans for action sequences, and then a reverse plan for a given action sequence is efficiently constructed online using this library. For the former part, we describe methods based on conformant planning; for the latter, we present a polynomial time algorithm.

Rectilinear Steiner Tree Construction Using Answer Set Programming.
Erdem, E.; and Wong, M. D. F.
In

Link bibtex abstract

*Logic Programming, 20th International Conference, ICLP 2004, Saint-Malo, France, September 6-10, 2004, Proceedings*, pages 386-399, 2004.Link bibtex abstract

@inproceedings{DBLP:conf/iclp/ErdemW04, author = {Esra Erdem and Martin D. F. Wong}, title = {Rectilinear Steiner Tree Construction Using Answer Set Programming}, booktitle = {Logic Programming, 20th International Conference, ICLP 2004, Saint-Malo, France, September 6-10, 2004, Proceedings}, year = {2004}, pages = {386-399}, ee = {http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=3132{\&}spage=386}, abstract = {We introduce a new method for Rectilinear Steiner Tree (RST) construction in a graph, using answer set programming. This method provides a formal representation of the problem as a logic program whose answer sets correspond to solutions. The answer sets for a logic program can be computed by special systems called answer set solvers. We describe the method for RST construction in the context of VLSI routing where multiple pins in a given placement of a chip are connected by an RST. Our method is different from the existing methods mainly in three ways. First, it always correctly determines whether a given RST routing problem is solvable, and it always produces a solution if one exists. Second, some enhancements of the basic problem, in which lengths of wires connecting the source pin to sink pins are restricted, can be easily represented by adding some rules. Our method guarantees to find a tree if one exists, even when the total wire length is not minimum. Third, routing problems with the presence of obstacles can be solved. With this approach, we have computed solutions to some RST routing problems using the answer set solver cmodels.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

We introduce a new method for Rectilinear Steiner Tree (RST) construction in a graph, using answer set programming. This method provides a formal representation of the problem as a logic program whose answer sets correspond to solutions. The answer sets for a logic program can be computed by special systems called answer set solvers. We describe the method for RST construction in the context of VLSI routing where multiple pins in a given placement of a chip are connected by an RST. Our method is different from the existing methods mainly in three ways. First, it always correctly determines whether a given RST routing problem is solvable, and it always produces a solution if one exists. Second, some enhancements of the basic problem, in which lengths of wires connecting the source pin to sink pins are restricted, can be easily represented by adding some rules. Our method guarantees to find a tree if one exists, even when the total wire length is not minimum. Third, routing problems with the presence of obstacles can be solved. With this approach, we have computed solutions to some RST routing problems using the answer set solver cmodels.

Plan reversals for recovery in execution monitoring.
Eiter, T.; Erdem, E.; and Faber, W.
In

Link bibtex abstract

*10th International Workshop on Non-Monotonic Reasoning (NMR 2004), Whistler, Canada, June 6-8, 2004, Proceedings*, pages 147-154, 2004.Link bibtex abstract

@inproceedings{DBLP:conf/nmr/EiterEF04, author = {Thomas Eiter and Esra Erdem and Wolfgang Faber}, title = {Plan reversals for recovery in execution monitoring}, booktitle = {10th International Workshop on Non-Monotonic Reasoning (NMR 2004), Whistler, Canada, June 6-8, 2004, Proceedings}, year = {2004}, pages = {147-154}, ee = {http://www.pims.math.ca/science/2004/NMR/papers/paper20.pdf}, abstract = {In this paper, we introduce a new method to recover from discrepancies in a general monitoring framework where the agent finds some explanations (points of failure) for discrepancies. According to this method, the agent finds a reverse plan to backtrack to a diagnosed point of failure and subsequently continues with the original plan. This method is appealing given that such a reverse plan is short with respect to the overall plan to be executed. While a reverse plan could be computed online by solving a planning problem, we present a potentially more efficient method: We first build offline a reverse plan library by finding reverse plans for action sequences, and then use this library online to construct reverse plans. The former part is done by reducing the problem of finding pairs of action sequences and reverse plans (of a certain length) to a conformant planning problem; for the latter, we present a polynomial time algorithm. Furthermore, we analyze the complexity of finding reverse plans, and obtain that the presented reduction is reasonable in general.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

In this paper, we introduce a new method to recover from discrepancies in a general monitoring framework where the agent finds some explanations (points of failure) for discrepancies. According to this method, the agent finds a reverse plan to backtrack to a diagnosed point of failure and subsequently continues with the original plan. This method is appealing given that such a reverse plan is short with respect to the overall plan to be executed. While a reverse plan could be computed online by solving a planning problem, we present a potentially more efficient method: We first build offline a reverse plan library by finding reverse plans for action sequences, and then use this library online to construct reverse plans. The former part is done by reducing the problem of finding pairs of action sequences and reverse plans (of a certain length) to a conformant planning problem; for the latter, we present a polynomial time algorithm. Furthermore, we analyze the complexity of finding reverse plans, and obtain that the presented reduction is reasonable in general.

2003
(2)

Reconstructing the Evolutionary History of Indo-European Languages Using Answer Set Programming.
Erdem, E.; Lifschitz, V.; Nakhleh, L.; and Ringe, D.
In

Link bibtex abstract

*Practical Aspects of Declarative Languages, 5th International Symposium, PADL 2003, New Orleans, LA, USA, January 13-14, 2003, Proceedings*, pages 160-176, 2003.Link bibtex abstract

@inproceedings{DBLP:conf/padl/ErdemLNR03, author = {Esra Erdem and Vladimir Lifschitz and Luay Nakhleh and Donald Ringe}, title = {Reconstructing the Evolutionary History of Indo-European Languages Using Answer Set Programming}, booktitle = {Practical Aspects of Declarative Languages, 5th International Symposium, PADL 2003, New Orleans, LA, USA, January 13-14, 2003, Proceedings}, year = {2003}, pages = {160-176}, ee = {http://link.springer.de/link/service/series/0558/bibs/2562/25620160.htm}, abstract = {The evolutionary history of languages can be modeled as a tree, called a phylogeny, where the leaves represent the extant languages, the internal vertices represent the ancestral languages, and the edges represent the genetic relations between the languages. Languages not only inherit characteristics from their ancestors but also sometimes borrow them from other languages. Such borrowings can be represented by additional non-tree edges. This paper addresses the problem of computing a small number of additional edges that turn a phylogeny into a ``perfect phylogenetic network''. To solve this problem, we use answer set programming, which represents a given computational problem as a logic program whose answer sets correspond to solutions. Using the answer set solver SMODELS, with some heuristics and optimization techniques, we have generated a few conjectures regarding the evolution of Indo-European languages.}, bibsource = {DBLP, http://dblp.uni-trier.de} }

The evolutionary history of languages can be modeled as a tree, called a phylogeny, where the leaves represent the extant languages, the internal vertices represent the ancestral languages, and the edges represent the genetic relations between the languages. Languages not only inherit characteristics from their ancestors but also sometimes borrow them from other languages. Such borrowings can be represented by additional non-tree edges. This paper addresses the problem of computing a small number of additional edges that turn a phylogeny into a ``perfect phylogenetic network''. To solve this problem, we use answer set programming, which represents a given computational problem as a logic program whose answer sets correspond to solutions. Using the answer set solver SMODELS, with some heuristics and optimization techniques, we have generated a few conjectures regarding the evolution of Indo-European languages.

Tight logic programs.
Erdem, E.; and Lifschitz, V.

bibtex abstract

*TPLP*, 3(4-5): 499-518. 2003.bibtex abstract

@article{DBLP:journals/tplp/ErdemL03, author = {Esra Erdem and Vladimir Lifschitz}, title = {Tight logic programs}, journal = {TPLP}, volume = {3}, number = {4-5}, year = {2003}, pages = {499-518}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {This note is about the relationship between two theories of negation as failure---one based on program completion, the other based on stable models, or answer sets. Francois Fages showed that if a logic program satisfies a certain syntactic condition, which is now called ``tightness,'' then its stable models can be characterized as the models of its completion. We extend the definition of tightness, and Fages' theorem, to programs with nested expressions in the bodies of rules, and study tight logic programs containing the definition of the transitive closure of a predicate. }, }

This note is about the relationship between two theories of negation as failure---one based on program completion, the other based on stable models, or answer sets. Francois Fages showed that if a logic program satisfies a certain syntactic condition, which is now called ``tightness,'' then its stable models can be characterized as the models of its completion. We extend the definition of tightness, and Fages' theorem, to programs with nested expressions in the bodies of rules, and study tight logic programs containing the definition of the transitive closure of a predicate.

2002
(1)

Theory and applications of answer set programming.
Erdem, E.
Ph.D. Thesis, Department of Computer Sciences, University of Texas at Austin, 2002.

N bibtex abstract

N bibtex abstract

@phdthesis{phdthesis, author = {Esra Erdem}, title = {Theory and applications of answer set programming}, year = {2002}, school = {Department of Computer Sciences, University of Texas at Austin}, abstract = {Answer set programming (ASP) is a new form of declarative logic programming. ASP interprets a logic program as a constraint on sets of literals, just as a propositional formula can be viewed as a constraint on assignments of truth values to atoms. The concept of an answer set was originally proposed as a semantics of negation as failure in Prolog. Instead of traditional Prolog systems, ASP uses answer set solvers. The input of Prolog consists of a logic program and a query, and Prolog computes answer substitutions; the input of an answer set solver is a logic program, and the solver computes the program's answer sets. The idea of ASP is to represent a given computational problem as a logic program whose answer sets correspond to solutions, and to use an answer set solver to find an answer set. We have investigated the application of ASP to several combinatorial search problems, including planning, wire routing, and phylogeny reconstruction. Planning is the problem of finding a sequence of actions that leads to a given goal. Wire routing is the problem of determining the physical locations of all wires interconnecting the circuit components on a chip. Phylogeny reconstruction is the problem of constructing and labeling an evolutionary tree for a set of taxa (taxonomic units), which describes the evolution of the taxa in that set from their most recent common ancestor. In our work on phylogeny reconstruction, we have generated several conjectures about the evolutionary history of Indo-European languages. The work on the use of ASP for planning has led us to the investigation of some theoretical questions related to answer sets. One is the problem of equivalent transformations of logic programs: under what conditions can we replace a program by an equivalent program that can be processed by an answer set solver more efficiently? Another problem is related to completion--a process that can translate a logic program into a set of formulas of classical logic. In some cases, the interpretations satisfying the completion of a program are also the answer sets for that program. In such cases, we can use propositional solvers--systems that compute a model of a given set of clauses--to find the program's answer sets. For some problems, propositional solvers are more efficient than answer set solvers. Therefore, we have investigated under what conditions we can use propositional solvers to find the program's answer sets.}, urlN = {dissertation.pdf}, }

Answer set programming (ASP) is a new form of declarative logic programming. ASP interprets a logic program as a constraint on sets of literals, just as a propositional formula can be viewed as a constraint on assignments of truth values to atoms. The concept of an answer set was originally proposed as a semantics of negation as failure in Prolog. Instead of traditional Prolog systems, ASP uses answer set solvers. The input of Prolog consists of a logic program and a query, and Prolog computes answer substitutions; the input of an answer set solver is a logic program, and the solver computes the program's answer sets. The idea of ASP is to represent a given computational problem as a logic program whose answer sets correspond to solutions, and to use an answer set solver to find an answer set. We have investigated the application of ASP to several combinatorial search problems, including planning, wire routing, and phylogeny reconstruction. Planning is the problem of finding a sequence of actions that leads to a given goal. Wire routing is the problem of determining the physical locations of all wires interconnecting the circuit components on a chip. Phylogeny reconstruction is the problem of constructing and labeling an evolutionary tree for a set of taxa (taxonomic units), which describes the evolution of the taxa in that set from their most recent common ancestor. In our work on phylogeny reconstruction, we have generated several conjectures about the evolutionary history of Indo-European languages. The work on the use of ASP for planning has led us to the investigation of some theoretical questions related to answer sets. One is the problem of equivalent transformations of logic programs: under what conditions can we replace a program by an equivalent program that can be processed by an answer set solver more efficiently? Another problem is related to completion--a process that can translate a logic program into a set of formulas of classical logic. In some cases, the interpretations satisfying the completion of a program are also the answer sets for that program. In such cases, we can use propositional solvers--systems that compute a model of a given set of clauses--to find the program's answer sets. For some problems, propositional solvers are more efficient than answer set solvers. Therefore, we have investigated under what conditions we can use propositional solvers to find the program's answer sets.

2001
(2)

Fages' Theorem for Programs with Nested Expressions.
Erdem, E.; and Lifschitz, V.
In

Link N bibtex abstract

*Logic Programming, 17th International Conference, ICLP 2001, Paphos, Cyprus, November 26 - December 1, 2001, Proceedings*, pages 242-254, 2001.Link N bibtex abstract

@inproceedings{DBLP:conf/iclp/ErdemL01, author = {Esra Erdem and Vladimir Lifschitz}, title = {Fages' Theorem for Programs with Nested Expressions}, booktitle = {Logic Programming, 17th International Conference, ICLP 2001, Paphos, Cyprus, November 26 - December 1, 2001, Proceedings}, year = {2001}, pages = {242-254}, ee = {http://link.springer.de/link/service/series/0558/bibs/2237/22370242.htm}, bibsource = {DBLP, http://dblp.uni-trier.de}, urlN = {iclp01.pdf}, abstract = {We extend a theorem by Francois Fages about the relationship between the completion semantics and the answer set semantics of logic programs to a class of programs with nested expressions permitted in the bodies of rules. Fages' theorem is important from the perspective of answer set programming: whenever the two semantics are equivalent, answer sets can be computed by propositional solvers, such as sato, instead of answer set solvers, such as smodels. The need to extend Fages' theorem to programs with nested expressions is related to the use of choice rules in the input language of smodels.}, }

We extend a theorem by Francois Fages about the relationship between the completion semantics and the answer set semantics of logic programs to a class of programs with nested expressions permitted in the bodies of rules. Fages' theorem is important from the perspective of answer set programming: whenever the two semantics are equivalent, answer sets can be computed by propositional solvers, such as sato, instead of answer set solvers, such as smodels. The need to extend Fages' theorem to programs with nested expressions is related to the use of choice rules in the input language of smodels.

Transitive Closure, Answer Sets and Predicate Completion.
And, E. E.; Erdem, E.; and Lifschitz, V.
In

N bibtex abstract

*Working notes of AAAI Spring Symposium*, pages 60-65, 2001.N bibtex abstract

@INPROCEEDINGS{And00transitiveclosure, author = {Esra Erdem And and Esra Erdem and Vladimir Lifschitz}, title = {Transitive Closure, Answer Sets and Predicate Completion}, booktitle = {Working notes of AAAI Spring Symposium}, year = {2001}, pages = {60-65}, urlN = {tc.pdf}, abstract = {We prove that the usual logic programming definition of transitive closure is correct under the answer set semantics, and investigate under what conditions it is correct under the completion semantics. That definition is allowed here to be combined with an arbitrary set of rules that may contain negation as failure, not merely with a set of facts. This work is motivated by applications to answer set programming.}, }

We prove that the usual logic programming definition of transitive closure is correct under the answer set semantics, and investigate under what conditions it is correct under the completion semantics. That definition is allowed here to be combined with an arbitrary set of rules that may contain negation as failure, not merely with a set of facts. This work is motivated by applications to answer set programming.

2000
(3)

Wire Routing and Satisfiability Planning.
Erdem, E.; Lifschitz, V.; and Wong, M. D. F.
In

Link N bibtex abstract

*Computational Logic - CL 2000, First International Conference, London, UK, 24-28 July, 2000, Proceedings*, pages 822-836, 2000.Link N bibtex abstract

@inproceedings{DBLP:conf/cl/ErdemLW00, author = {Esra Erdem and Vladimir Lifschitz and Martin D. F. Wong}, title = {Wire Routing and Satisfiability Planning}, booktitle = {Computational Logic - CL 2000, First International Conference, London, UK, 24-28 July, 2000, Proceedings}, year = {2000}, pages = {822-836}, ee = {http://link.springer.de/link/service/series/0558/bibs/1861/18610822.htm}, bibsource = {DBLP, http://dblp.uni-trier.de}, urlN = {cl00.pdf}, abstract = {Wire routing is the problem of determining the physical locations of all wires interconnecting the circuit components on a chip. Since the wires cannot intersect with each other, they are competing for limited spaces, thus making routing a difficult combinatorial optimization problem. We present a new approach to wire routing that uses action languages and satisfiability planning. Its idea is to think of each path as the trajectory of a robot, and to understand a routing problem as the problem of planning the actions of several robots whose paths are required to be disjoint. The new method differs from the algorithms implemented in the existing routing systems in that it always correctly determines whether a given problem is solvable, and it produces a solution whenever one exists.}, }

Wire routing is the problem of determining the physical locations of all wires interconnecting the circuit components on a chip. Since the wires cannot intersect with each other, they are competing for limited spaces, thus making routing a difficult combinatorial optimization problem. We present a new approach to wire routing that uses action languages and satisfiability planning. Its idea is to think of each path as the trajectory of a robot, and to understand a routing problem as the problem of planning the actions of several robots whose paths are required to be disjoint. The new method differs from the algorithms implemented in the existing routing systems in that it always correctly determines whether a given problem is solvable, and it produces a solution whenever one exists.

A New Declarative Bias for ILP: Construction Modes.
Erdem, E.; and Flener, P.
In

Link bibtex abstract

*Inductive Logic Programming, 10th International Conference, ILP 2000, Work-in-progress reports, London, UK, July 2000, Proceedings*, 2000.Link bibtex abstract

@inproceedings{DBLP:conf/ilp/ErdemF00, author = {Esra Erdem and Pierre Flener}, title = {A New Declarative Bias for ILP: Construction Modes}, booktitle = {Inductive Logic Programming, 10th International Conference, ILP 2000, Work-in-progress reports, London, UK, July 2000, Proceedings}, year = {2000}, ee = {http://SunSITE.Informatik.RWTH-Aachen.DE/Publications/CEUR-WS/Vol-35/05-ErdemFlener.ps}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {Inductive logic programming (ILP) systems use some declarative bias to constrain the hypothesis space. We introduce a new declarative bias, called construction modes, capturing the required dataflow of a relation, and design a language for expressing such construction modes . Their semantics is captured via the notion of admissibility. Experiments with the ILP systems SYNAPSE and DIALOGS have established the usefulness of construction modes. Since the new bias is orthogonal to the existing search biases, it can be used in conjunction with the existing biases. }, }

Inductive logic programming (ILP) systems use some declarative bias to constrain the hypothesis space. We introduce a new declarative bias, called construction modes, capturing the required dataflow of a relation, and design a language for expressing such construction modes . Their semantics is captured via the notion of admissibility. Experiments with the ILP systems SYNAPSE and DIALOGS have established the usefulness of construction modes. Since the new bias is orthogonal to the existing search biases, it can be used in conjunction with the existing biases.

Fages' Theorem and Answer Set Programming.
Babovich, Y.; Erdem, E.; and Lifschitz, V.
In

Link bibtex abstract

*Proc. of the 8th International Workshop on Non-Monotonic Reasoning (NMR'00)*, 2000.Link bibtex abstract

@inproceedings{DBLP:journals/corr/cs-AI-0003042, author = {Yuliya Babovich and Esra Erdem and Vladimir Lifschitz}, title = {Fages' Theorem and Answer Set Programming}, booktitle = {Proc. of the 8th International Workshop on Non-Monotonic Reasoning (NMR'00)}, year = {2000}, ee = {http://arxiv.org/abs/cs.AI/0003042}, bibsource = {DBLP, http://dblp.uni-trier.de}, abstract = {We generalize a theorem by Francois Fages that describes the relationship between the completion semantics and the answer set semantics for logic programs with negation as failure. The study of this relationship is important in connection with the emergence of answer set programming. Whenever the two semantics are equivalent, answer sets can be computed by a satisfiability solver, and the use of answer set solvers such as SMODELS and DLV is unnecessary. A logic programming representation of the blocks world due to Ilkka Niemela is discussed as an example.}, }

We generalize a theorem by Francois Fages that describes the relationship between the completion semantics and the answer set semantics for logic programs with negation as failure. The study of this relationship is important in connection with the emergence of answer set programming. Whenever the two semantics are equivalent, answer sets can be computed by a satisfiability solver, and the use of answer set solvers such as SMODELS and DLV is unnecessary. A logic programming representation of the blocks world due to Ilkka Niemela is discussed as an example.

1999
(4)

Transformations of Logic Programs Related to Causality and Planning.
Erdem, E.; and Lifschitz, V.
In

Link N bibtex abstract

*Logic Programming and Nonmonotonic Reasoning, 5th International Conference, LPNMR'99, El Paso, Texas, USA, December 2-4, 1999, Proceedings*, pages 107-116, 1999.Link N bibtex abstract

@inproceedings{DBLP:conf/lpnmr/ErdemL99, author = {Esra Erdem and Vladimir Lifschitz}, title = {Transformations of Logic Programs Related to Causality and Planning}, booktitle = {Logic Programming and Nonmonotonic Reasoning, 5th International Conference, LPNMR'99, El Paso, Texas, USA, December 2-4, 1999, Proceedings}, year = {1999}, pages = {107-116}, ee = {http://link.springer.de/link/service/series/0558/bibs/1730/17300107.htm}, bibsource = {DBLP, http://dblp.uni-trier.de}, urlN = {lpnmr99.pdf}, abstract = {We prove two properties of logic programs under the answer set semantics that may be useful in connection with applications of logic programming to representing causality and to planning. One theorem is about the use of disjunctive rules to express that an atom is exogenous. The other provides an alternative way of expressing that a plan does not include concurrently executed actions.}, }

We prove two properties of logic programs under the answer set semantics that may be useful in connection with applications of logic programming to representing causality and to planning. One theorem is about the use of disjunctive rules to express that an atom is exogenous. The other provides an alternative way of expressing that a plan does not include concurrently executed actions.

Completing Open Logic Programs by Constructive Induction.
Erdem, E.; and Flener, P.

Paper bibtex abstract

*International Journal of Intelligent Systems*, 14(10): 995-1019. 1999.Paper bibtex abstract

@article{erdem-comp, author = "E. Erdem and P. Flener", title = "Completing Open Logic Programs by Constructive Induction", text = "E. Erdem and P. Flener. Completing Open Logic Programs by Constructive Induction. Submitted.", journal = {International Journal of Intelligent Systems}, number = {10}, volume = {14}, pages = {995-1019}, year = {1999}, url = {http://www3.interscience.wiley.com/journal/63501004/abstract}, abstract = {We consider part of the problem of schema-biased inductive synthesis of recursive logic programs from incomplete specifications, such as clausal evidence (for instance, but not necessarily, ground positive and negative examples). After synthesizing the base clause and introducing recursive call(s) to the recursive clause, it remains to combine the overall result from the partial results obtained through recursion, so as to complete the recursive clause. Evidence for this combination relation can be abduced from the initially given evidence for the top-level relation. A program for this combination relation can be anything, from a single clause performing a unification (such as for lastElem) to multiple guarded clauses performing unifications (such as for filtering programs) to recursive programs (such as for naive reverse). Existing methods cannot induce guarded clause programs for this combination relation from the abduced evidence. Some existing methods cannot even detect that the combination program itself may have to be recursive and thus they then do not recursively invoke themselves the overall recursive program synthesizer. We introduce our Program Completion Method as a suitable extension and generalization of the existing methods.}, }

We consider part of the problem of schema-biased inductive synthesis of recursive logic programs from incomplete specifications, such as clausal evidence (for instance, but not necessarily, ground positive and negative examples). After synthesizing the base clause and introducing recursive call(s) to the recursive clause, it remains to combine the overall result from the partial results obtained through recursion, so as to complete the recursive clause. Evidence for this combination relation can be abduced from the initially given evidence for the top-level relation. A program for this combination relation can be anything, from a single clause performing a unification (such as for lastElem) to multiple guarded clauses performing unifications (such as for filtering programs) to recursive programs (such as for naive reverse). Existing methods cannot induce guarded clause programs for this combination relation from the abduced evidence. Some existing methods cannot even detect that the combination program itself may have to be recursive and thus they then do not recursively invoke themselves the overall recursive program synthesizer. We introduce our Program Completion Method as a suitable extension and generalization of the existing methods.

A new heuristic to use least generalizations in ILP.
Erdem, E.
1999.
Unpublished draft

N bibtex abstract

N bibtex abstract

@misc{unpub1, author = {Esra Erdem}, title = { A new heuristic to use least generalizations in {ILP}}, note = {Unpublished draft}, urlN = {lgg.pdf}, year = {1999}, abstract = {The classical least generalization of a set C of clauses is a single clause. Such a unique clause is sometimes too general wrt some over-generality criterion, and this undesired situation may lead to memorization of the clauses in C at the end of learning process. Current ILP systems apply some heuristic algorithms to refine this situation where the classical definition of least generalization is used as an operator in a search space throughout the learning. Our approach to this problem is different: we use the classical least generalization of C in a more declarative way to narrow the search-space at the very beginning of the learning algorithm, that is, we define the concept of least generalization of a set C of clauses in a different way as being a minimal-sized set of clauses, each member of this set being the classical least generalization of some subset of C. The elements of these subsets are two by two compatible, in the sense that their classical least generalizations are not too general according to the over-generality criterion admissibility. We give an efficient algorithm for computing this re-defined concept, providing thus a new approach to disjunctive concept learning. We also prove a few theorems relating the problem-independent concept of compatibility with the problem-specific concept of admissibility: these theorems show how to speed up certain computations for these concepts. Finally, we outline an application of these considerations to a frequently occurring problem in the inductive synthesis of recursive (logic) programs, namely the induction of the operator combining the partial results (obtained through recursion) into the overall result. }, }

The classical least generalization of a set C of clauses is a single clause. Such a unique clause is sometimes too general wrt some over-generality criterion, and this undesired situation may lead to memorization of the clauses in C at the end of learning process. Current ILP systems apply some heuristic algorithms to refine this situation where the classical definition of least generalization is used as an operator in a search space throughout the learning. Our approach to this problem is different: we use the classical least generalization of C in a more declarative way to narrow the search-space at the very beginning of the learning algorithm, that is, we define the concept of least generalization of a set C of clauses in a different way as being a minimal-sized set of clauses, each member of this set being the classical least generalization of some subset of C. The elements of these subsets are two by two compatible, in the sense that their classical least generalizations are not too general according to the over-generality criterion admissibility. We give an efficient algorithm for computing this re-defined concept, providing thus a new approach to disjunctive concept learning. We also prove a few theorems relating the problem-independent concept of compatibility with the problem-specific concept of admissibility: these theorems show how to speed up certain computations for these concepts. Finally, we outline an application of these considerations to a frequently occurring problem in the inductive synthesis of recursive (logic) programs, namely the induction of the operator combining the partial results (obtained through recursion) into the overall result.

Applications of logic programs to planning: computational experiments.
Erdem, E.
1999.
Unpublished Draft

Paper N bibtex abstract

Paper N bibtex abstract

@misc{unpub2, author = {Esra Erdem}, title = { Applications of logic programs to planning: computational experiments}, note = {Unpublished Draft}, year = {1999}, url = {http://people.sabanciuniv.edu/esraerdem/experiments/experiments.html}, urlN = {experiments.pdf}, abstract = {This report summarizes experiments with the systems SMODELS and DLV applied to some planning problems. The planning problems are presented to SMODELS and DLV as logic programs. Plans correspond to answer sets for these programs, in the spirit of answer set programming.}, }

This report summarizes experiments with the systems SMODELS and DLV applied to some planning problems. The planning problems are presented to SMODELS and DLV as logic programs. Plans correspond to answer sets for these programs, in the spirit of answer set programming.

1997
(1)

A re-definition of least generalizations, and construction modes as a new declarative bias for ILP.
Erdem, E.
Technical Report BU-CEIS-9718, Bilkent University, 1997.

N bibtex abstract

N bibtex abstract

@techreport{ErdFle98, author = {Esra Erdem}, title = {A re-definition of least generalizations, and construction modes as a new declarative bias for {ILP}}, institution = {Bilkent University}, year = {1997}, number = {BU-CEIS-9718}, urlN = {ErdFle98.pdf}, abstract = {The classical definition of the concept of least generalization of a clause set C is that it is a _single_ clause. Since such a unique clause is sometimes over-general, we re-define this concept as being a minimal-sized _set_ of clauses, each member of this set being the classical least generalization of some subset of C. The elements of these subsets are two by two compatible, in the sense that their classical least generalizations are not too general according to some over-generality criterion. We give an algorithm for computing this re-defined concept, providing thus a new approach to disjunctive concept learning. The criterion for over-generality is problem-specific. We introduce a new such criterion: two clauses are compatible, i.e., their classical least generalization is not over-general, if this least generalization is admissible wrt a construction mode capturing the required dataflow of each involved relation. We design a language for expressing such construction modes, and we define a powerful admissibility criterion. We also prove a few theorems relating the problem-independent concept of compatibility with the problem-specific concept of admissibility (our over-generality criterion): these theorems show how to speed up certain computations for these concepts. Finally, we outline an application of these considerations to a frequently occurring problem in the inductive synthesis of recursive (logic) programs, namely the induction of the operator combining the partial results (obtained through recursion) into the overall result.}, }

The classical definition of the concept of least generalization of a clause set C is that it is a _single_ clause. Since such a unique clause is sometimes over-general, we re-define this concept as being a minimal-sized _set_ of clauses, each member of this set being the classical least generalization of some subset of C. The elements of these subsets are two by two compatible, in the sense that their classical least generalizations are not too general according to some over-generality criterion. We give an algorithm for computing this re-defined concept, providing thus a new approach to disjunctive concept learning. The criterion for over-generality is problem-specific. We introduce a new such criterion: two clauses are compatible, i.e., their classical least generalization is not over-general, if this least generalization is admissible wrt a construction mode capturing the required dataflow of each involved relation. We design a language for expressing such construction modes, and we define a powerful admissibility criterion. We also prove a few theorems relating the problem-independent concept of compatibility with the problem-specific concept of admissibility (our over-generality criterion): these theorems show how to speed up certain computations for these concepts. Finally, we outline an application of these considerations to a frequently occurring problem in the inductive synthesis of recursive (logic) programs, namely the induction of the operator combining the partial results (obtained through recursion) into the overall result.

1996
(1)

An MSG-method for inductive logic program synthesis.
Erdem, E.
1996.
Senior Project Final Report

N bibtex abstract

N bibtex abstract

@misc{senior, author = {Esra Erdem}, title = {An {MSG}-method for inductive logic program synthesis}, note = {Senior Project Final Report}, year = {1996}, urlN = {senior_project.pdf}, abstract = {SYNAPSE2 is an upgraded version of SYNAPSE (developed by Flener [1995]), which is an implementation of an inductive synthesis mechanism that semi-automatically synthesizes divide-and-conquer logic algorithms in a schema-guided way, from non-incrementally given examples and properties of an intended relation. SYNAPSE2 goes through six steps, instantiating the place-holders of a chosen divide-and-conquer logic algorithm schema. At Step 5, the MSG-Method is used as a tool. The MSG-Method is used to infer a logic algorithm of an intended relation, if it is possible to get a logic algorithm using only =/2 predicate in the body. In this project, our aim is to simplify and extend the existing MSG-Method (introduced by Flener [1995]) independent of the place-holder and its schema, and to re-implement Step 5 of SYNAPSE2, which corresponds to the steps 5 and 6 of SYNAPSE. In this report, the main concepts are introduced as preliminaries in Section 1, the synthesis mechanism is explained with an example (in SYNAPSE2) in Section 2, the MSG-Method is focused on in Section 3, after then Step 5 is explained in Section 4, finally the project is discussed in Section 5. }, }

SYNAPSE2 is an upgraded version of SYNAPSE (developed by Flener [1995]), which is an implementation of an inductive synthesis mechanism that semi-automatically synthesizes divide-and-conquer logic algorithms in a schema-guided way, from non-incrementally given examples and properties of an intended relation. SYNAPSE2 goes through six steps, instantiating the place-holders of a chosen divide-and-conquer logic algorithm schema. At Step 5, the MSG-Method is used as a tool. The MSG-Method is used to infer a logic algorithm of an intended relation, if it is possible to get a logic algorithm using only =/2 predicate in the body. In this project, our aim is to simplify and extend the existing MSG-Method (introduced by Flener [1995]) independent of the place-holder and its schema, and to re-implement Step 5 of SYNAPSE2, which corresponds to the steps 5 and 6 of SYNAPSE. In this report, the main concepts are introduced as preliminaries in Section 1, the synthesis mechanism is explained with an example (in SYNAPSE2) in Section 2, the MSG-Method is focused on in Section 3, after then Step 5 is explained in Section 4, finally the project is discussed in Section 5.

# Embedding in another Page

Copy&paste any of the following snippets into an existing page to embed this page. For more details see the documention.

**JavaScript**(Easiest)

```
<script src="https://bibbase.org/show?bib=193.255.135.175/papers/krrpublications.bib&group0=year&jsonp=1"></script>
```

**PHP**

```
<?php
$contents = file_get_contents("https://bibbase.org/show?bib=193.255.135.175/papers/krrpublications.bib&group0=year");
print_r($contents);
?>
```

**iFrame**

```
<iframe src="https://bibbase.org/show?bib=193.255.135.175/papers/krrpublications.bib&group0=year"></iframe>
```