Recently, there has been an increasing interest in the bottom-up evaluation of the semantics of logic programs with complex terms. The presence of function symbols in the program may render the ground instantiation in...
详细信息
Recently, there has been an increasing interest in the bottom-up evaluation of the semantics of logic programs with complex terms. The presence of function symbols in the program may render the ground instantiation infinite, and finiteness of models and termination of the evaluation procedure, in the general case, are not guaranteed anymore. Since the program termination problem is undecidable in the general case, several decidable criteria (called program termination criteria) have been recently proposed. However, current conditions are not able to identify even simple programs, whose bottom-up execution always terminates. The paper introduces new decidable criteria for checking termination of logic programs with function symbols under bottom-up evaluation, by deeply analyzing the program structure. First, we analyze the propagation of complex terms among arguments by means of the extended version of the argument graph called propagation graph. The resulting criterion, called G-acyclicity, generalizes most of the decidable criteria proposed so far. Next, we study how rules may activate each other and define a more powerful criterion, called safety. This criterion uses the so-called safety function able to analyze how rules may activate each other and how the presence of some arguments in a rule limits its activation. We also study the application of the proposed criteria to bound queries and show that the safety criterion is well-suited to identify relevant classes of programs and bound queries. Finally, we propose a hierarchy of classes of terminating programs, called k-safety, where the k-safe class strictly includes the (k-1)-safe class.
We investigate the control of evaluation strategies in a variant of the lambda-calculus derived through the Curry-Howard correspondence from LJF, a sequent calculus for intuitionistic logic implementing the focusing t...
详细信息
ISBN:
(纸本)9781450335164
We investigate the control of evaluation strategies in a variant of the lambda-calculus derived through the Curry-Howard correspondence from LJF, a sequent calculus for intuitionistic logic implementing the focusing technique. The proof theory of focused intuitionistic logic yields a single calculus in which a number of known lambda-calculi appear as subsystems obtained by restricting types to a certain fragment of LJF. In particular, standard lambda-calculi as well as the call-by-push-value calculus are analysed using this framework, and we relate cut elimination for LJF to a new abstract machine subsuming well-known machines for these different strategies.
We propose a timed and soft extension of Concurrent Constraint programming. The time extension is based on the hypothesis of bounded asynchrony: The computation takes a bounded period of time and is measured by a disc...
详细信息
We propose a timed and soft extension of Concurrent Constraint programming. The time extension is based on the hypothesis of bounded asynchrony: The computation takes a bounded period of time and is measured by a discrete global clock. Action prefixing is then considered as the syntactic marker that distinguishes a time instant from the next one. Supported by soft constraints instead of crisp ones, tell and ask agents are now equipped with a preference (or consistency) threshold, which is used to determine their success or suspension. In this paper, we provide a language to describe the agents' behavior, together with its operational and denotational semantics, for which we also prove the compositionality and correctness properties. After presenting a semantics using maximal parallelism of actions, we also describe a version for their interleaving on a single processor (with maximal parallelism for time elapsing). Coordinating agents that need to take decisions on both preference values and time events may benefit from this language.
This paper provides a gentle introduction to problem-solving with the IDP3 system. The core of IDP3 is a finite model generator that supports first-order logic enriched with types, inductive definitions, aggregates an...
详细信息
This paper provides a gentle introduction to problem-solving with the IDP3 system. The core of IDP3 is a finite model generator that supports first-order logic enriched with types, inductive definitions, aggregates and partial functions. It offers its users a modeling language that is a slight extension of predicate logic and allows them to solve a wide range of search problems. Apart from a small introductory example, applications are selected from problems that arose within machine learning and data mining research. These research areas have recently shown a strong interest in declarative modeling and constraint-solving as opposed to algorithmic approaches. The paper illustrates that the IDP3 system can be a valuable tool for researchers with such an interest. The first problem is in the domain of stemmatology, a domain of philology concerned with the relationship between surviving variant versions of text. The second problem is about a somewhat related problem within biology where phylogenetic trees are used to represent the evolution of species. The third and final problem concerns the classical problem of learning a minimal automaton consistent with a given set of strings. For this last problem, we show that the performance of our solution comes very close to that of the state-of-the art solution. For each of these applications, we analyze the problem, illustrate the development of a logic-based model and explore how alternatives can affect the performance.
Although Boolean Constraint Technology has made tremendous progress over the last decade, the efficacy of state-of-the-art solvers is known to vary considerably across different types of problem instances, and is know...
详细信息
Although Boolean Constraint Technology has made tremendous progress over the last decade, the efficacy of state-of-the-art solvers is known to vary considerably across different types of problem instances, and is known to depend strongly on algorithm parameters. This problem was addressed by means of a simple, yet effective approach using handmade, uniform, and unordered schedules of multiple solvers in ppfolio, which showed very impressive performance in the 2011 Satisfiability Testing (SAT) Competition. Inspired by this, we take advantage of the modeling and solving capacities of Answer Set programming (ASP) to automatically determine more refined, that is, nonuniform and ordered solver schedules from the existing benchmarking data. We begin by formulating the determination of such schedules as multi-criteria optimization problems and provide corresponding ASP encodings. The resulting encodings are easily customizable for different settings, and the computation of optimum schedules can mostly be done in the blink of an eye, even when dealing with large runtime data sets stemming from many solvers on hundreds to thousands of instances. Also, the fact that our approach can be customized easily enabled us to swiftly adapt it to generate parallel schedules for multi-processor machines.
Model flattening often introduces many auxiliary variables. We provide a way to eliminate some of the auxiliary variables occurring in exactly two constraints by replacing those two constraints by a new equivalent con...
详细信息
ISBN:
(纸本)9783319232195;9783319232188
Model flattening often introduces many auxiliary variables. We provide a way to eliminate some of the auxiliary variables occurring in exactly two constraints by replacing those two constraints by a new equivalent constraint for which a propagator is automatically generated on the fly. Experiments show that, despite the overhead of the preprocessing and of using machine-generated propagators, eliminating auxiliary variables often reduces the solving time.
Streamlined constraint reasoning is the addition of uninferred constraints to a constraint model to reduce the search space, while retaining at least one solution. Previously, effective streamlined models have been co...
详细信息
ISBN:
(纸本)9783319232195;9783319232188
Streamlined constraint reasoning is the addition of uninferred constraints to a constraint model to reduce the search space, while retaining at least one solution. Previously, effective streamlined models have been constructed by hand, requiring an expert to examine closely solutions to small instances of a problem class and identify regularities. We present a system that automatically generates many conjectured regularities for a given Essence specification of a problem class by examining the domains of decision variables present in the problem specification. These conjectures are evaluated independently and in conjunction with one another on a set of instances from the specified class via an automated modelling tool-chain comprising of Conjure, Savile Row and Minion. Once the system has identified effective conjectures they are used to generate streamlined models that allow instances of much larger scale to be solved. Our results demonstrate good models can be identified for problems in combinatorial design, Ramsey theory, graph theory and group theory - often resulting in order of magnitude speed-ups.
One of the big challenges in the development of probabilistic relational (or probabilistic logical) modeling and learning frameworks is the design of inference techniques that operate on the level of the abstract mode...
详细信息
One of the big challenges in the development of probabilistic relational (or probabilistic logical) modeling and learning frameworks is the design of inference techniques that operate on the level of the abstract model representation language, rather than on the level of ground, propositional instances of the model. Numerous approaches for such "lifted inference" techniques have been proposed. While it has been demonstrated that these techniques will lead to significantly more efficient inference on some specific models, there are only very recent and still quite restricted results that show the feasibility of lifted inference on certain syntactically defined classes of models. Lower complexity bounds that imply some limitations for the feasibility of lifted inference on more expressive model classes were established earlier in Jaeger (2000;Jaeger, M. 2000. On the complexity of inference about probabilistic relational models. Artificial Intelligence 117, 297-308). However, it is not immediate that these results also apply to the type of modeling languages that currently receive the most attention, i.e., weighted, quantifier-free formulas. In this paper we extend these earlier results, and show that under the assumption that NETIME not equal ETIME, there is no polynomial lifted inference algorithm for knowledge bases of weighted, quantifier-, and function-free formulas. Further strengthening earlier results, this is also shown to hold for approximate inference and for knowledge bases not containing the equality predicate.
In this paper, we apply Fangzhen Lin's methodology of computer aided theorem discovery to discover classes of strongly equivalent logic programs with negation as failure in the head. Specifically, with the help of...
详细信息
ISBN:
(纸本)9783319251592;9783319251585
In this paper, we apply Fangzhen Lin's methodology of computer aided theorem discovery to discover classes of strongly equivalent logic programs with negation as failure in the head. Specifically, with the help of computers, we discover exact conditions that capture the strong equivalence between small sets of rules, which have potential applications in the theory and practice of logic programming. In the experiment, we extend the previous approach to semi-automatically generate plausible conjectures. We also show that it is possible to divide the original problem in simpler cases and combine their solutions in order to obtain the solution of the original problem.
Vehicular network is regarded as an important part of the Intelligent Transportation System (ITS). However, with the increasing number of vehicular applications, it is a challenge to meet the demands of both communica...
详细信息
ISBN:
(纸本)9781509032068
Vehicular network is regarded as an important part of the Intelligent Transportation System (ITS). However, with the increasing number of vehicular applications, it is a challenge to meet the demands of both communication and computation. Fog computing can provide mobile users with the demanded services through low latency and short-distance local connections. This paper investigates the optimal deployment and dimensioning (ODD) of fog computing supported vehicular network. The ODD problem is important for fog computing from theory to practical deployment. We formulate the problem as an integer linear programming (ILP) and the objective is to minimize the cost of deployment. Two different models based on coupling and decoupling fog devices with Roadside Units (RSUs) are developed and the results show that the decoupling model is a way more cost-effective in practice.
暂无评论