We establish optimal bounds on the number of nested propagation steps in k-consistency tests. It is known that local consistency algorithms such as arc-, path- and k-consistency are not efficiently parallelizable. The...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
We establish optimal bounds on the number of nested propagation steps in k-consistency tests. It is known that local consistency algorithms such as arc-, path- and k-consistency are not efficiently parallelizable. Their inherent sequential nature is caused by long chains of nested propagation steps, which cannot be executed in parallel. This motivates the question "What is the minimum number of nested propagation steps that have to be performed by k-consistency algorithms on (binary) constraint networks with n variables and domain size d?" It was known before that 2-consistency requires Omega(nd) and 3-consistency requires Omega(n(2)) sequential propagation steps. We answer the question exhaustively for every k >= 2: there are binary constraint networks where any k-consistency procedure has to perform Omega( n(k-1)d(k-1)) nested propagation steps before local inconsistencies were detected. This bound is tight, because the overall number of propagation steps performed by k-consistency is at most n(k-1)d(k-1).
We revisit the SeqBin constraint [1]. This meta-constraint subsumes a number of important global constraints like Change [2], Smooth [3] and IncreasingNValue [4]. We show that the previously proposed filtering algorit...
详细信息
The proceedings contain 11 papers. The special focus in this conference is on principles andpractice of Semantic Web Reasoning. The topics include: On subtyping of tree-structured data;towards generic query, update, ...
ISBN:
(纸本)3540229612
The proceedings contain 11 papers. The special focus in this conference is on principles andpractice of Semantic Web Reasoning. The topics include: On subtyping of tree-structured data;towards generic query, update, and event languages for the semantic web;data retrieval and evolution on the semantic web;rules and queries with ontologies;semantic web reasoning for ontology-based integration of resources;static type-checking of datalog with ontologies;reasoning about temporal context using ontology and abductive constraint logic programming;towards a multi-calendar temporal type system for semantic web query languages;calendrical calculations with time partitionings and fuzzy time intervals;a defeasible logic system for the semantic web and a PDDL based tool for automatic web service composition.
A fundamental area of software engineering that remains a challenge is the delivery of software with the minimum of remaining defects. The principal technique currently used in the software industry for the verificati...
详细信息
ISBN:
(纸本)9780954414511
A fundamental area of software engineering that remains a challenge is the delivery of software with the minimum of remaining defects. The principal technique currently used in the software industry for the verification and validation of software is dynamic software testing where the software under consideration is actually executed using test data. The actual generation of test data for the purpose of automated software testing is still however mainly a manual task. This problem is further compounded for Java programmers because testing criteria can be imposed at the Java Bytecode level rather than at the source level. To alleviate these difficulties an Interactive Bytecode Inspection System (IBIS) has been developed that allows examination of the Java Bytecode and the automatic generation and execution of test data.
The concurrent constraintprogramming paradigm and linear logic are studied. The characterization of the success stores or the constraints of terminal configurations with no suspended agent, requires restricting the d...
详细信息
ISBN:
(纸本)1581132654
The concurrent constraintprogramming paradigm and linear logic are studied. The characterization of the success stores or the constraints of terminal configurations with no suspended agent, requires restricting the deductions that can be carried-out to forbid logical deletions of agents by weakening. Linear constraint systems greatly enhance the expressive power of concurrent constraintprogramming.
The natural representation of solutions of finite constraint satisfaction problems is as a (set of) function(s) or relation(s). In (constraint) logic programming, answers are in the form of substitutions to the variab...
详细信息
ISBN:
(纸本)1581132654
The natural representation of solutions of finite constraint satisfaction problems is as a (set of) function(s) or relation(s). In (constraint) logic programming, answers are in the form of substitutions to the variables in the query. This results in a not very declarative programming style where a table has to be presented as a complex term. Recently, stable logic programming, also called answer set programming and abductive logic programming have been proposed as approaches supporting a more declarative style for solving such problems. The approach developed in this paper is to extend the constraint domain of a constraint logic programming language with open functions, functions for which the interpretation is not fixed in advance. Their interpretation contains the solution of the problem. This enrichment of the constraint domain yields a language which is almost as expressive as abductive logic programming and is very well suited for expressing finite domain constraint satisfaction problems. Implementation requires only to extend the constraint solver of the underlying CLP language.
We present a method for approximating the semantics of probabilistic programs to the purpose of constructing semantics-based analyses of such programs. The method resembles the one based on Galois connection as develo...
详细信息
ISBN:
(纸本)1581132654
We present a method for approximating the semantics of probabilistic programs to the purpose of constructing semantics-based analyses of such programs. The method resembles the one based on Galois connection as developed in the Cousot framework for abstract interpretation. The main difference between our approach and the standard theory of abstract interpretation is the choice of linear space structures instead of order-theoretic ones as semantical (concrete and abstract) domains. We show that our method generates "best approximations" according to an appropriate notion of precision defined in terms of a norm. Moreover, if re-casted in a order-theoretic setting these approximations are correct in the sense of classical abstract interpretation theory. We use Concurrent constraintprogramming as a reference programming paradigm. The basic concepts and ideas can nevertheless be applied to any other paradigm. The results we present, are intended to be the first step towards a general theory of probabilistic abstract interpretation, which re-formulates the classical theory in a setting suitable for a quantitative reasoning about programs.
The proceedings contain 61 papers. The special focus in this conference is on principles andpractice of constraintprogramming. The topics include: On confluence of constraint handling rules;a labelling arc consisten...
ISBN:
(纸本)3540615512
The proceedings contain 61 papers. The special focus in this conference is on principles andpractice of constraintprogramming. The topics include: On confluence of constraint handling rules;a labelling arc consistency method for functional constraints;constraint satisfaction in optical routing for passive wavelength-routed networks;using CSP look-back techniques to solve exceptionally hard SAT instances;the independence property of a class of set constraints;speeding up constraint propagation by redundant modeling;a constraint-based interactive train rescheduling tool;local search and the number of solutions;derivation of constraints and database relations;an efficient and practical approach to solving the job-shop problem;an instance of adaptive constraint propagation;an empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem;empirical studies of heuristic local search for constraint solving;inference duality as a basis for sensitivity analysis;a framework for solving constraint hierarchies;transformations between HCLP and PCSP;a test for tractability;tractable disjunctions of linear constraints;exploiting the use of DAC in MAX-CSP;a new approach for weighted constraint satisfaction;towards a more efficient stochastic constraint solver;a view of local search in constraintprogramming;from quasi-solutions to solution;existential variables and local consistency in finite domain constraint problems;logical semantics of concurrent constraintprogramming;solving non-binary convex CSPs in continuous domains;an experimental comparison of three modified deltablue algorithms;constraint logic programming over unions of constraint theories and on query languages for linear queries definable with polynomial constraints.
暂无评论