Forbidden patterns problems are a generalisation of (finite) constraint satisfaction problems which are definable in Feder and Vardi's logic MMSNP [1]. in fact, they are examples of infinite constraint satisfactio...
详细信息
ISBN:
(纸本)9783642153952
Forbidden patterns problems are a generalisation of (finite) constraint satisfaction problems which are definable in Feder and Vardi's logic MMSNP [1]. in fact, they are examples of infinite constraint satisfaction problems with nice model theoretic properties introduced by Bodirsky [2]. In previous work [3], we introduced a normal form for these forbidden patterns problems which allowed us to provide an effective characterisation of when a problem is a finite or infinite constraint satisfaction problem. One of the central concepts of this normal form is that of a recolouring. In the presence of a recolouring from a forbidden patterns problem Omega(1) to another forbidden patterns problem Omega(2), containment of Omega(1) in Omega(2) follows. the converse does not hold in general and it remained open whether it did in the case of problems being given in our normal form. In this paper, we prove that this is indeed the case. We also show that the recolouring problem is Pi(p)(2)-harpd and in Sigma(p)(3).
Temporal logics are a well investigated formalism for the specification, verification, and synthesis of reactive systems. Within this family, alternating temporal logic, ATL*, has been introduced as a useful generaliz...
详细信息
ISBN:
(纸本)9783642175107
Temporal logics are a well investigated formalism for the specification, verification, and synthesis of reactive systems. Within this family, alternating temporal logic, ATL*, has been introduced as a useful generalization of classical linear- and branching-time temporal logics by allowing temporal operators to be indexed by coalitions of agents. Classically, temporal logics are memoryless: once a path in the computation tree is quantified at a given node, the computation that has led to that node is forgotten. Recently, mCTL* has been defined as a memoryful variant of CTL*, where path quantification is memoryful. In the context of multi-agent planning, memoryful quantification enables agents to "relent" and change their goals and strategies depending on their past history. In this paper, we define mATL*, a memoryful extension of ATL*, in which a formula is satisfied at a certain node of a path by taking into account boththe future and the past. We study the expressive power of mATL*, its succinctness, as well as related decision problems. We also investigate the relationship between memoryful quantification and past modalities and show their equivalence. We show that boththe memoryful and the past extensions come without any computational price;indeed, we prove that boththe satisfiability and the model-checking problems are 2EXPTIME-COMPLETE, as they are for ATL*.
Many tasks in combinatorial computation admit a natural formulation as instances of the exact cover problem. We observe that the exact cover problem can in turn be compactly translated to the satisfiability (SAT) prob...
详细信息
ISBN:
(纸本)9783642153952
Many tasks in combinatorial computation admit a natural formulation as instances of the exact cover problem. We observe that the exact cover problem can in turn be compactly translated to the satisfiability (SAT) problem, allowing the basic Davis-Putnam-Logemann-Loveland procedure with no clause learning to linearly simulate backtrack search for exact cover. this SAT-based approach is empirically compared with a widely applied backtrack search algorithm, Knuth's "Dancing Links X" algorithm, on a set of benchmark problems arising in combinatorial enumeration. the experimental results indicate that the current model-counting SAT solvers are in general superior in pruning the search space, but still need to be optimized for running time.
Hardware transactional memory (HTM) is a promising technology to improve the productivity of parallel programming. However, a general agreement has not been reached on the consumability of HTM. User experiences indica...
详细信息
ISBN:
(纸本)9783642152900
Hardware transactional memory (HTM) is a promising technology to improve the productivity of parallel programming. However, a general agreement has not been reached on the consumability of HTM. User experiences indicate that HTM interface is not straightforward to be adopted by programmers to parallelize existing commercial applications, because of the internal limitation of HTM and the difficulties to identify shared variables hidden in the code. In this paper we demonstrate that, with well-designed encapsulation, HTM can deliver good consumability. Based on the study of a typical commercial application in supply chain simulations - GBSE, we develop a general scheduling engine that encapsulates the HTM interface. Withthe engine, we can convert the sequential program to multi-threaded model without changing any source code for the simulation logic. the time spent on parallelization is reduced from two months to one week, and the performance is close to the manually tuned counterpart with fine-grained locks.
the proceedings contain 36 papers. the topic discussed include: challenges to machine learning: relations between reality and appearance;first-order probabilistic languages: into the unknown;integration of learning an...
详细信息
ISBN:
(纸本)9783540738466
the proceedings contain 36 papers. the topic discussed include: challenges to machine learning: relations between reality and appearance;first-order probabilistic languages: into the unknown;integration of learning and reasoning techniques;injecting life with computers;on the connection between the phase transition of the covering test and the learning success rate;revising probabilistic Prolog programs;inductivelogicprogramming for gene regulation prediction;generalized ordering-search for learning directed probabilistic logical models;extension of the top-down data driven strategy to ILP;learning recursive patterns for biomedical information extraction;towards learning nonrecursive LPADs by transforming them into Bayesian networks;multi-class prediction using stochastic logic programs;structuring natural language data by learning rewriting rules;and an efficient algorithm for computing kernel function defined with anti-unification.
this paper presents a deductive object oriented framework that is capable to model P2P networks. the framework is superimposed over a basic language based on modules. A small set of operators are logically defined and...
详细信息
we present in this wor. the analysis, investigation and experimental measurements for a High Data Rate (HDR), modulator design for biodevice telemetry over wireless inductive coupling. that has been achieving by progr...
详细信息
Several learning systems based on Inverse Entailment (IE) have been proposed, some that compute single clause hypotheses, exemplified by Progol, and others that, produce multiple clauses in response to a single seed e...
详细信息
ISBN:
(纸本)9783642042379
Several learning systems based on Inverse Entailment (IE) have been proposed, some that compute single clause hypotheses, exemplified by Progol, and others that, produce multiple clauses in response to a single seed example. A common denominator of these systems, is a restricted hypothesis search space, within which each clause must individually explain some example E, or some member of an abductive explanation for E. this paper proposes a new IE approach, called Induction on Failure (IoF), that generalises existing Horn clause learning systems by allowing the computation of hypotheses within a larger search space, namely that of Connected theories. A proof procedure for IoF is proposed that generalises existing IE systems and also resolves Yamamoto's example. A prototype implementation is also described. Finally, a semantics is presented called Connected theory Generalisation, which is proved to extend Kernel Set Subsumption and to include hypotheses constructed within this new IoF approach.
this paper presents a deductive object oriented framework that is capable to model P2P networks. the framework is superimposed over a basic language based on modules. A small set of operators are logically defined and...
详细信息
this paper presents a deductive object oriented framework that is capable to model P2P networks. the framework is superimposed over a basic language based on modules. A small set of operators are logically defined and semantically justified in terms of the basic logicprogramming semantics. Nodes in the network correspond to objects that can exchange messages.
We present in this work the analysis, investigation and experimental measurements for a high data rate (HDR), modulator design for biodevice telemetry over wireless inductive coupling. that has been achieving by progr...
详细信息
ISBN:
(纸本)9781424450909;9781424450916
We present in this work the analysis, investigation and experimental measurements for a high data rate (HDR), modulator design for biodevice telemetry over wireless inductive coupling. that has been achieving by programming a code description and implementation on an FPGA/CLPD. A new VHDL designed n-PSK modulator programmed with VHDL code generates digital BPSK, QPSK and 8PSK signals. However, comparing to the conventional analogue modulators, this type of modulator offers the flexibility to reconfigure and upgrade. the system has been designed to operate from inductively coupled RF power. Furthermore, we propose a modified a hybrid class E/F power amplifier system design, working at low radio frequency; in this work it is 135 KHz for modulated RF power with ASK modulator. the minimum magnetic field and powering range of the reader is considered in detail. the prototype system has been solved and performance simulated by using Matlab/ Simulink and was evaluated by lab measurement.
暂无评论