检索结果-内蒙古大学图书馆

Parallel instantiation of ASP programs: techniques and experiments

theory and practice of logic programming 2013年第02期13卷 253-278页

作者： Perri, Simona Ricca, Francesco Sirianni, Marco Univ Calabria Dipartimento Matemat I-87030 Arcavacata Di Rende Italy

Answer-Set programming (ASP) is a powerful logic-based programming language, which is enjoying increasing interest within the scientific community and (very recently) in industry. The evaluation of Answer-Set Programs is traditionally carried out in two steps. At the first step, an input program P undergoes the so-called instantiation (or grounding) process, which produces a program P' semantically equivalent to P, but not containing any variable;in turn, P' is evaluated by using a backtracking search algorithm in the second step. It is well-known that instantiation is important for the efficiency of the whole evaluation, might become a bottleneck in common situations, is crucial in several real-world applications, and is particularly relevant when huge input data have to be dealt with. At the time of this writing, the available instantiator modules are not able to exploit satisfactorily the latest hardware, featuring multi-core/multi-processor Symmetric MultiProcessing technologies. This paper presents some parallel instantiation techniques, including load-balancing and granularity control heuristics, which allow for the effective exploitation of the processing power offered by modern Symmetric MultiProcessing machines. This is confirmed by an extensive experimental analysis reported herein.

关键词： Answer-Set programming Instantiation Parallelism Heuristics

来源：评论

学校读者我要写书评

暂无评论

A Model Transformation Language Based on logic programming

引用

39th Conference on Current Trends in theory and practice of Computer Science (SOFSEM)

作者： Almendros-Jimenez, Jesus M. Iribarne, Luis Univ Almeria Dept Lenguajes & Computac Almeria 04120 Spain

ISBN: (纸本)9783642358432

In this paper we present a model transformation language based on logic programming. The language, called PTL (Prolog based Transformation Language), can be considered as a hybrid language in which ATL-style rules are combined with logic rules for defining transformations. The proposal has been implemented so that a Prolog program is automatically obtained from a PTL program. We have equipped our language with debugging and tracing capabilities which help developers to detect programming errors in PTL rules.

关键词： logic programming

来源：评论

学校读者我要写书评

暂无评论

Consistent query answering via ASP from different perspectives: theory and practice

引用

theory and practice of logic programming 2013年第02期13卷 227-252页

作者： Manna, Marco Ricca, Francesco Terracina, Giorgio Univ Calabria Dept Math I-87036 Cosenza Italy

A data integration system provides transparent access to different data sources by suitably combining their data, and providing the user with a unified view of them, called global schema. However, source data are generally not under the control of the data integration process;thus, integrated data may violate global integrity constraints even in the presence of locally consistent data sources. In this scenario, it may be anyway interesting to retrieve as much consistent information as possible. The process of answering user queries under global constraint violations is called consistent query answering (CQA). Several notions of CQA have been proposed, e.g., depending on whether integrated information is assumed to be sound, complete, exact, or a variant of them. This paper provides a contribution in this setting: it uniforms solutions coming from different perspectives under a common Answer-Set programming (ASP)-based core, and provides query-driven optimizations designed for isolating and eliminating inefficiencies of the general approach for computing consistent answers. Moreover, the paper introduces some new theoretical results enriching existing knowledge on the decidability and complexity of the considered problems. The effectiveness of the approach is evidenced by experimental results.

关键词： Answer-Set programming data integration consistent query answering

来源：评论

学校读者我要写书评

暂无评论

Compiling Input* FO(.) inductive definitions into tabled prolog rules for IDP3

引用

theory and practice of logic programming 2013年第4-5期13卷 691-704页

作者： Jansen, Joachim Jorissen, Albert Janssens, Gerda Katholieke Univ Leuven Dept Comp Sci Louvain Belgium

FO(.)(IDP3) extends first-order logic with inductive definitions, partial functions, types and aggregates. Its model generator IDP3 first grounds the theory and then uses search to find the models. The grounder uses Lifted Unit Propagation (LUP) to reduce the size of the groundings of problem specifications in IDP3. LUP is in general very effective, but performs poorly on definitions of predicates whose two-valued interpretation can be computed from data in the input structure. To solve this problem, a preprocessing step is introduced that converts such definitions to Prolog code and uses XSB Prolog to compute their interpretation. The interpretation of these predicates is then added to the input structure, their definitions are removed from the theory and further processing is done by the standard IDP3 system. Experimental results show the effectiveness of our method.

关键词： program transformation FO(.) logic programming tabling knowledge base systems IDP system declarative modeling

来源：评论

学校读者我要写书评

暂无评论

Region-based memory management for Mercury programs

引用

theory and practice of logic programming 2013年第6期13卷 959-1024页

作者： Phan, Quan Janssens, Gerda Somogyi, Zoltan Katholieke Univ Leuven Dept Comp Sci B-3001 Louvain Belgium Univ Melbourne Natl ICT Australia Melbourne Vic 3010 Australia Univ Melbourne Dept Comp Sci & Software Engn Melbourne Vic 3010 Australia

Region-based memory management (RBMM) is a form of compile time memory management, well-known from the world of functional programming. In this paper we describe our work on implementing RBMM for the logic programming language Mercury. One interesting point about Mercury is that it is designed with strong type, mode, and determinism systems. These systems not only provide Mercury programmers with several direct software engineering benefits, such as self-documenting code and clear program logic, but also give language implementors a large amount of information that is useful for program analyses. In this work, we make use of this information to develop program analyses that determine the distribution of data into regions and transform Mercury programs by inserting into them the necessary region operations. We prove the correctness of our program analyses and transformation. To execute annotated programs, we have implemented runtime support that tackles the two main challenges posed by backtracking. First, backtracking can require regions removed during forward execution to be "resurrected";and second, any memory allocated during computation that has been backtracked over must be recovered promptly without waiting for the regions involved to come to the end of their life. We describe in detail our solution of both these problems. We study in detail how our RBMM system performs on a selection of benchmark programs, including some well-known difficult cases for RBMM. Even with these difficult cases, our RBMM-enabled Mercury system obtains clearly faster runtimes for 15 out of 18 benchmarks compared to the base Mercury system with its Boehm runtime garbage collector, with an average runtime speedup of 24%, and an average reduction in memory requirements of 95%. In fact, our system achieves optimal memory consumption in some programs.

关键词： region-based memory management region analysis runtime support backtracking logic programming Mercury

来源：评论

学校读者我要写书评

暂无评论

A declarative approach to distributed computing: Specification, execution and analysis

引用

theory and practice of logic programming 2013年第4-5期13卷 815-830页

作者： Ma, Jiefei Le, Franck Wood, David Russo, Alessandra Lobo, Jorge Imperial Coll London London England IBM Corp Waston Lab Armonk NY 10504 USA ICREA Univ Pompeu Fabra Barcelona Spain

There is an increasing interest in using logic programming to specify and implement distributed algorithms, including a variety of network applications. These are applications where data and computation are distributed among several devices and where, in principle, all the devices can exchange data and share the computational results of the group. In this paper we propose a declarative approach to distributed computing whereby distributed algorithms and communication models can be (i) specified as action theories of fluents and actions;(ii) executed as collections of distributed state machines, where devices are abstracted as (input/output) automata that can exchange messages;and (iii) analysed using existing results on connecting causal theories and Answer Set programming. Results on the application of our approach to different classes of network protocols are also presented.

关键词： action theory answer set programming network protocols distributed computing

来源：评论

学校读者我要写书评

暂无评论

Reasoning with Forest logic Programs and f-hybrid knowledge bases

引用

theory and practice of logic programming 2013年第3期13卷 395-463页

作者： Feier, Cristina Heymans, Stijn Vienna Univ Technol Inst Informat Syst Knowledge Based Syst Grp A-1040 Vienna Austria

Open Answer Set programming (OASP) is an undecidable framework for integrating ontologies and rules. Although several decidable fragments of OASP have been identified, few reasoning procedures exist. In this paper, we provide a sound, complete, and terminating algorithm for satisfiability checking w.r.t. Forest logic Programs (FoLPs), a fragment of OASP where rules have a tree shape and allow for inequality atoms and constants. The algorithm establishes a decidability result for FoLPs. Although believed to be decidable, so far only the decidability for two small subsets of FoLPs, local FoLPs and acyclic FoLPs, has been shown. We further introduce f-hybrid knowledge bases, a hybrid framework where SHOD knowledge bases and FoLPs coexist, and we show that reasoning with such knowledge bases can be reduced to reasoning with FoLPs only. We note that f-hybrid knowledge bases do not require the usual (weakly) DL-safety of the rule component, thus providing a genuine alternative approach to current integration approaches of ontologies and rules.

关键词： Forest logic Programs finite model property f-hybrid knowledge bases open answer sets integration of rules and ontologies

来源：评论

学校读者我要写书评

暂无评论

An Algebraic Presentation of Predicate logic

An Algebraic Presentation of Predicate Logic

引用

16th International Conference on Foundations of Software Science and Computation Structures (FOSSACS) Held as Part of the European Joint Conferences on theory and practice of Software (ETAPS)

作者： Staton, Sam Univ Cambridge Comp Lab Cambridge England

ISBN: (纸本)9783642370755;9783642370748

We present an algebraic theory for a fragment of predicate logic. The fragment has disjunction, existential quantification and equality. It is not an algebraic theory in the classical sense, but rather within a new framework that we call 'parameterized algebraic theories'. We demonstrate the relevance of this algebraic presentation to computer science by identifying a programming language in which every type carries a model of the algebraic theory. The result is a simple functional logic programming language. We provide a syntax-free representation theorem which places terms in bijection with sieves, a concept from category theory. We study presentation-invariance for general parameterized algebraic theories by providing a theory of clones. We show that parameterized algebraic theories characterize a class of enriched monads.

关键词： Algebraic Presentation Predicate logic existential quantification

来源：评论

学校读者我要写书评

暂无评论

Expressiveness of communication in answer set programming

引用

theory and practice of logic programming 2013年第3期13卷 361-394页

作者： Bauters, Kim Schockaert, Steven Janssen, Jeroen Vermeir, Dirk De Cock, Martine Univ Ghent Dept Appl Math & Comp Sci B-9000 Ghent Belgium Vrije Univ Brussel Dept Comp Sci B-1050 Brussels Belgium

Answer set programming (ASP) is a form of declarative programming that allows to succinctly formulate and efficiently solve complex problems. An intuitive extension of this formalism is communicating ASP, in which multiple ASP programs collaborate to solve the problem at hand. However, the expressiveness of communicating ASP has not been thoroughly studied. In this paper, we present a systematic study of the additional expressiveness offered by allowing ASP programs to communicate. First, we consider a simple form of communication where programs are only allowed to ask questions to each other. For the most part, we deliberately consider only simple programs, i.e. programs for which computing the answer sets is in P. We find that the problem of deciding whether a literal is in some answer set of a communicating ASP program using simple communication is NP-hard. In other words, due to the ability of these simple ASP programs to communicate and collaborate, we move up a step in the polynomial hierarchy. Second, we modify the communication mechanism to also allow us to focus on a sequence of communicating programs, where each program in the sequence may successively remove some of the remaining models. This mimics a network of leaders, where the first leader has the first say and may remove models that he or she finds unsatisfactory. Using this particular communication mechanism allows us to capture the entire polynomial hierarchy. This means, in particular, that communicating ASP could be used to solve problems that are above the second level of polynomial hierarchy, such as some forms of abductive reasoning as well as PSPACE-complete problems such as STRIPS planning.

关键词： logic programming answer set programming multi-agent reasoning

来源：评论

学校读者我要写书评

暂无评论

Compiling Input* FO(.) inductive definitions into tabled prolog rules for IDP3

<i>Compiling Input</i>* FO(.) <i>inductive definitions into ...

引用

29th International Conference on logic programming ICLP

作者： Jansen, Joachim Jorissen, Albert Janssens, Gerda Katholieke Univ Leuven Dept Comp Sci Louvain Belgium

关键词： program transformation FO(.) logic programming tabling knowledge base systems IDP system declarative modeling

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：