this paper represents the beginning of a study aimed at devising semantic models for true concurrency that provide clear distinctions between concurrency, paxallelism and choice. We present a simple programming langua...
详细信息
ISBN:
(纸本)3540665366
this paper represents the beginning of a study aimed at devising semantic models for true concurrency that provide clear distinctions between concurrency, paxallelism and choice. We present a simple programming language which includes (weakly) sequential composition, asynchronous and synchronous parallel composition, a restriction operator, and that supports recursion. We develop an operational and a denotational semantics for this language, and we obtain a theorem relating the behavior of a process as described by the transition system to the meaning of the process in the denotational model. this implies that the denotational model is adequate with respect to the operational model. Our denotational model is based on the resource traces of Gastin and Teodesiu, and since a single resource trace represents all possible executions of a concurrent process, we axe able to model each term of our concurrent language by a single trace. therefore we obtain a deterministic semantics for our language and we axe able to model parallelism without introducing nondeterminism.
Declarative programming has been classically used for solving computational problems regarding AI, knowledge representation and so on. During the last decade, Soft-Computing has emerged as a new application area speci...
详细信息
ISBN:
(纸本)9783319192581;9783319192574
Declarative programming has been classically used for solving computational problems regarding AI, knowledge representation and so on. During the last decade, Soft-Computing has emerged as a new application area specially tempting for those new generation declarative languages integrating fuzzy logic into logicprogramming. In many fuzzy logicprogramming languages, both program clauses and connective definitions admit a clear declarative, rule-based representation inspired by the well-known logic and functional programming paradigms, respectively. A powerful and promising proposal in this area is represented by the multi-adjoint logicprogramming approach (for which we have developed the FLOPER tool), where a set of (logic) Prolog-like rules are accompanied with a set of (functional) Haskell-like fuzzy connective definitions for manipulating truth degrees beyond the simpler case of {true, false}. Since these definitions can be seen as a particular case of equations and/or rewrite rules typically used in functional programming, in this paper we focus on their optimization by reusing some variants of program transformation techniques based on unfolding with a functional taste, which have been largely exploited in this last crisp (not fuzzy) setting. We also show how our method rebounds in the simplification of some computational cost measures we proposed in the past. Our approach is accompanied with some implementation and practical issues in connection withthe SYNth and FLOPER tools and the fuzzyX-Path application we have developed in the area of the semantic web.
this paper introduces a propositional encoding for lexicographic path orders in connection with dependency pairs. this facilitates the application of SAT solvers for termination analysis of term rewrite systems based ...
详细信息
ISBN:
(纸本)3540482814
this paper introduces a propositional encoding for lexicographic path orders in connection with dependency pairs. this facilitates the application of SAT solvers for termination analysis of term rewrite systems based on the dependency pair method. We address two main inter-related issues and encode them as satisfiability problems of propositional formulas that can be efficiently handled by SAT solving: (1) the combined search for a lexicographic path order together with an argument filtering to orient a set of inequalities;and (2) how the choice of the argument filtering influences the set of inequalities that have to be oriented. We have implemented our contributions in the termination prover AProVE. Extensive experiments show that by our encoding and the application of SAT solvers one obtains speedups in orders of magnitude as well as increased termination proving power.
the theory BV of bit-vectors, i.e. fixed-size arrays of bits equipped with standard low-level machine instructions, is becoming very popular in formal verification. Standard solvers for this theory are based on a bit-...
详细信息
ISBN:
(纸本)9783642120015
the theory BV of bit-vectors, i.e. fixed-size arrays of bits equipped with standard low-level machine instructions, is becoming very popular in formal verification. Standard solvers for this theory are based on a bit-level encoding into propositional logic and SAT-based resolution techniques. In this paper, we investigate an alternative approach based on a word-level encoding into bounded arithmetic and Constraint logicprogramming (CLP) resolution techniques. We define an original CLP framework (domains and propagators) dedicated to bit-vector constraints. this framework is implemented in a prototype and thorough experimental studies have been conducted. the new approach is shown to perform much better than standard CLP-based approaches, and to considerably reduce the gap withthe best SAT-based BV solvers.
We introduce a novel diagnostic reasoning method for robotic systems with multiple robots, to find the causes of observed discrepancies relevant for plan execution. Our method proposes (i) a systematic modification of...
详细信息
the ever-rising expectations of customers regarding quality and diversity of products require new products to be launched with a minimum of upheaval and consequently rapid, defect-free and economical processes. these ...
详细信息
the ever-rising expectations of customers regarding quality and diversity of products require new products to be launched with a minimum of upheaval and consequently rapid, defect-free and economical processes. these goals can be attained and guaranteed in the planning departments of businesses through the sharing of secure and up-to-date planning data. leading to a high degree of flexibility and a minimum of interruptions in the production processes. In terms of technology planning, this results in a demand for economic methods of planning and NC programming, leading in turn to continuous, systematic acquisition of specialised in-house technological knowledge. However, most of the applications on the market are unsatisfactory in terms of acquisition of specialised knowledge of technology, only allowing specialised planning knowledge to be gathered or entered through costly procedures and for it to be organised statically. For rational processing and evaluation of planning knowledge, it is therefore sensible to systematically record technological discoveries made in the course of the planning and running-in process and to make them available for future planning processes. this processing of empirical knowledge along with rational and safe technology planning is supported by the use of DP systems, thus enabling planning knowledge to be kept constantly up-to-date, growing along withthe data specific to the enterprise, Fur this purpose, a suitable information model must be devised that represents the integration point within the NC process chain. Using a feature-based product model introduced in the design departments as a starting point, the model is extended to take in a production-orientated view. the model should be designed in such a way that, above all, the technological interconnections are represented and that the technology planning, NC programming and running-in process are integrated through the model. In order to evaluate and process empirical knowledge? m
Constructing parsimonious phylogenetic trees from species data is a central problem in phylogenetics, and has diverse applications, even outside biology. Many variations of the problem, including the cladistic Camin-S...
详细信息
ISBN:
(纸本)3540482814
Constructing parsimonious phylogenetic trees from species data is a central problem in phylogenetics, and has diverse applications, even outside biology. Many variations of the problem, including the cladistic Camin-Sokal (CCS) version, are NP-complete. We present Answer Set programming (ASP) models for the binary CCS problem, as well as a simpler perfect phylogeny version, along with experimental results of applying the models to biological data. Our contribution is three-fold. First, we solve phylogeny problems which have not previously been tackled by ASP. Second, we report on variants of our CCS model which significantly. affect run time, including the interesting case of making the program "slightly tighter". this version exhibits some of the best performance, in contrast with a tight version of the model which exhibited poor performance. third, we are able to find proven-optimal solutions for larger instances of the CCS problem than the widely used branch-and-bound-based PHYLIP package.
It is well-known that heuristic search in ILP is prone to plateau phenomena. An explanation can be given after the work of Giordana and Saitta: the ILP covering test is NP-complete and therefore exhibits a sharp phase...
详细信息
It is well-known that heuristic search in ILP is prone to plateau phenomena. An explanation can be given after the work of Giordana and Saitta: the ILP covering test is NP-complete and therefore exhibits a sharp phase transition in its coverage probability. As the heuristic value of a hypothesis depends on the number of covered examples, the regions "yes" and "no" represent plateaus that need to be crossed during search without an informative heuristic value. Several subsequent works have extensively studied this finding by running several learning algorithms on a large set of artificially generated problems and argued that the occurrence of this phase transition dooms every learning algorithm to fail to identify the target concept. We note however that only generate-and-test learning algorithms have been applied and that this conclusion has to be qualified in the case of data-driven learning algorithms. Mostly building on the pioneering work of Winston on near-miss examples, we show that, on the same set of problems, a top-down data-driven strategy can cross any plateau if near-misses are supplied in the training set, whereas they do not change the plateau profile and do not guide a generate-and-test strategy. We conclude that the location of the target concept with respect to the phase transition alone is not a reliable indication of the learning problem difficulty as previously thought.
Many real-life problems in Supply Chain (SC) are over-constrained. Insufficient resources and time requirements result in an inability to all constraints. In some cases, their fulfillment requires very intensive compu...
详细信息
ISBN:
(纸本)9783319401621;9783319401614
Many real-life problems in Supply Chain (SC) are over-constrained. Insufficient resources and time requirements result in an inability to all constraints. In some cases, their fulfillment requires very intensive computing. One way to overcome these difficulties is to soften some of the constraints. Natural environment for the modeling and solving of problems with constraints is constraint programming (CP), which is, however, ineffective on optimization problems and constraints containing a sum of many decision variables. this is when the idea to hybridize CP and other environments originated. the article presents the concept of modeling and solving soft constraints in SC problems using the hybrid approach. the illustrative example provided in the paper illustrates effectiveness and possibilities of this approach.
Possibilistic logic is a well-known logic for reasoning under uncertainty, which is based on the idea that the epistemic state of an agent can be modeled by assigning to each possible world a degree of possibility, ta...
详细信息
暂无评论