EXACT LEARNING OF FIRST-ORDER EXPRESSIONS FROM QUERIES
- Marta Arias; C○ Marta Arias
This thesis studies the complexity of learning logical expressions in the model of Exact Learning from Membership and Equivalence Queries. The focus is on Horn expressions in first order logic but results for propositional logic are also derived. The thesis includes several contributions towards characterizing the complexity of learning in these contexts. First, a new algorithm for learning first order Horn expressions is presented and proved correct. The algorithm improves on previous work in two ways. It can learn a larger class of expressions than previously known, and its query and time complexity improve on previous algorithms. In particular the...
Polynomial certificates for propositional classes, in
- Marta Arias; Aaron Feigelson; Roni Khardon; Rocco A. Servedio
This paper studies the complexity of learning classes of expressions in propositional logic from equivalence queries and membership queries. In particular, we focus on bounding the number of queries that are required to learn the class ignoring computational complexity. This quantity is known to be captured by a combinatorial measure of concept classes known as the certificate complexity. The paper gives new constructions of polynomial size certificates for monotone expressions in conjunctive normal form (CNF), for unate CNF functions where each variable affects the function either positively or negatively but not both ways, and for Horn CNF functions. Lower bounds...
The problem of constrained judgment aggregation
- Franz Dietrich; Christian List
Group decisions must often obey exogenous constraints. While in a preference aggregation problem constraints are modelled by restricting the set of feasible alternatives, this paper addresses the modelling of constraints when aggregating individual yes/no judgments on interconnected propositions. For example, court judgments in breach-of-contract cases should respect the constraint that action and obligation are necessary and sufficient for liability, and judgments on budget items should respect budgetary constraints. In this paper, we make constraints in judgment aggregation explicit by relativizing the rationality conditions of consistency and deductive closure to a constraint set, whose variation yields more or less strong notions...
Partial model completion in model driven engineering using constraint logic programming
- Sagar Sen; Benoit Baudry; Doina Precup
Abstract. In Model Driven Engineering a model is a graph of objects that conforms to a meta-model and a set of constraints. The meta-model and the constraints declaratively restrict models to a valid set. Models are used to represent the state and behaviour of software systems. They are specified in visual modelling environments or automatically synthesized for program testing. In such applications, a modeller is interested in specifying a partial model or a set of partial models which has a structure and associated properties that interests him/her. Completing a partial model manually can be an extremely tedious or an undecidable...
2010 IEEE 26-th Convention of Electrical and Electronics Engineers in Israel Power Grid Analysis Based on a Macro Circuit Model
- Shahar Kvatinsky; Eby G. Friedman; Avinoam Kolodny; Levi Schächter
Abstract—Analysis and design of on-chip power grids are complex problems. A typical grid consists of hundreds of millions of transistors that act as current consumers. Typical algorithms for power grid analysis or power grid automatic design, model the current consumers, namely the CMOS logic gates, as ideal current sources. In this study we offer a new methodology for modeling the power-consuming gates on the grid. Our approach is based on the analysis of the total dissipated power by these consumers. We propose a new model for the current consumers, based on effective impedance. In this model, only passive elements are...
Notes prepared by
- Stanley Burris
The monument to the work initiated by Boole, the algebraization of logic, is the three volumes Algebra der Logik by Schröder (1841–1902), which appeared in the years 1890–1910, filling over 2,000 pages. Although the spirit of the subject came from the work of Boole and De Morgan, Schröder’s volumes are really a tribute to the work of C.S. Peirce, along with Schröder’s contributions. In addition to the substantial job of organizing the literature, the lasting contributions of Schröder’s volumes are 1) his emphasis on the Elimination Problem and 2) his fine presentation of the Calculus of Binary Relations. Volumes I...
H. Shin z
- R. I. Bahar Y; M. Burns Z; G. D. Hachtel Z; E. Macii X; F. Somenzi Z
This paper presents a novel technique for re-synthesizing circuits for low-power dissipation. Power consumption is reduced through redundancy addition and removal by using learning to identify indirect logic implications within a circuit. Such implications are exploited by adding gates and connections to the circuit without altering its overall behavior and thereby enabling us to eliminate other, high power dissipating, nodes. We propose a new BDD-based method for computing indirect implications in a logic network; furthermore, we present heuristic techniques to perform redundancy addition and removal without destroying the topology of the mapped circuit. Experimental results show the e ectiveness of...
- Stanley Burris; Thoralf Skolem
1919- Investigation on the axioms of the calculus of classes and on product and sum problems which are connected with certain classes of statements. 1920- Logico-combinatorial investigations on the satisfiability and provability of mathematical theorems plus a theorem on dense sets. 1922- Some remarks on the axiomatic formulation of set theory. 1928- On mathematical logic. The 1919 paper
MRL – Memristor Ratioed Logic
- Shahar Kvatinsky; Nimrod Wald; Guy Satat; Avinoam Kolodny; Uri C. Weiser
Abstract — Memristive devices are novel structures, developed primarily as memory. Another interesting application for memristive devices is logic circuits. In this paper, MRL (Memristor Ratioed Logic)- a hybrid CMOS-memristive logic family- is described. In this logic family, OR and AND logic gates are based on memristive devices, and CMOS inverters are added to provide a complete logic structure and signal restoration. Unlike previously published memristive-based logic families, the MRL family is compatible with standard CMOS logic. A case study of an eight-bit full adder is presented and related design considerations are discussed. I.
Countable Countermodels: Löwenheim.
- Stanley Burris
• opened the door to the serious study of model theory by bringing in the size of an infinite model of a first-order sentence • gave a canonical procedure to build a countable countermodel to a first-order sentence – this initiated some of the most popular work in automated theorem proving (mainly attributed to Herbrand) • showed that statements in the first-order predicate calculus (with equality) for monadic predicates which were valid in finite domains were valid in all domains • pointed out that first-order relational logic with equality was adequate to express all mathematical problems • showed that one...
Logic Synthesis using Power-Sensitive Don’t Care Sets
- Christopher K. Lennard; Premal Buch; A. Richard Newton
The Boolean space spanned by the primary input vectors of a combinational function may contain a large variance in minterm probabilities. By partitioning the Don’t Care set into regions strongly and weakly influential upon switching activity we exploit this variance to bias area-optimization towards reduced power dissipation. Experimental results indicate that our method can reduce power dissipation of a combinational CMOS circuit with no penalty in area. 1
Notes prepared by
- Stanley Burris
In Chapter II of LMCS we looked at the propositional proof system PC and resolution theorem proving. A number of ideas have been developed regarding just how one sets up the basic structure of a proof system. We will look at some of the main ones here. 1.1 Definition of a propositional logic DEFINITION 1 A propositional logic 1 consists of • S, a set of connectives • C, the associated algebra of connectives • X, a set of propositional variables • C, a set of propositional constants • T(X), the set of propositional formulas over X • Axioms •...
- Eliseo Fernández
Recent reflections by several authors on the evolution of Peirce’s conception of the symbol have shed new light on this semiotic and logic centerpiece of Peircean thought. Here I use Peirce’s equally central notion of habit to show connections between these reflections and such currently debated philosophical issues as the notion of emergence, the nature of causation and the recently introduced biological conception of evolvability, as well as new developments issuing from the nascent discipline of biosemiotics.
Masking at Gate Level in the Presence of
- Berndt M. Gammel
Abstract. It has recently been shown that logic circuits in the implementation of cryptographic algorithms, although protected by “secure” random masking schemes, leak side-channel information, which can be exploited in differential power attacks . The leak is due to the fact that the mathematical models describing the gates neglected multiple switching of the outputs of the gates in a single clock cycle. This effect, however, is typical for CMOS circuits and known as glitching. Hence several currently known masking schemes are not secure in theory or practice. Solutions for DPA secure circuits based on logic styles which do not show...
The Backend Duplication Method: A Leakage-Proof Place-and-Route Strategy for ASICs
- Sylvain Guilley; Yves Mathieu; Renaud Pacalet
Abstract. Several types of logic gates suitable for leakage-proof computations have been put forward [1–4]. This paper describes a method, called “backend duplication ” to assemble secured gates into leakage-proof cryptoprocessors. To the authors ’ knowledge, this article is the first CADoriented publication to address all the aspects involved in the backend design of secured hardware. The “backend duplication ” method achieves the place-and-route of differential netlists. It allows for 100 % placement density and for balanced routing of dual-rail signals. Wires of every other metal layer are free to make turns. In addition, the method does not require any...
FIRST ORDER DECISION DIAGRAMS FOR DECISION THEORETIC PLANNING
- Saket Joshi; C Saket Joshi
Compact representations of complex knowledge form the core of solutions to many problems in Artificial Intelligence. Sequential decision making under uncertainty is one such important problem and Decision Theoretic Planning (DTP) has been one of the most successful frameworks for this task. Recent advances in DTP have focused on generating efficient solutions for Relational Markov Decision Processes (RMDP), a formulation that models problems that are naturally described using objects and relations among them. The core contribution of this thesis is the introduction of compact representation schemes for functions over relational structures, and associated algorithms that together lead to efficient solutions...
Bounded Model Checking Approaches for Verification of Distributed Time Petri Nets
- Wojciech Penczek; Agata Półrola; Andrzej Zbrzezny, et al.
We consider two symbolic approaches to bounded model checking (BMC) of distributed time Petri nets (DTPNs). We focus on the properties expressed in Linear Temporal Logic without the neXt-time operator (LTL−X) and the existential fragment of Computation Tree Logic without the neXt-time operator (ECTL−X). We give a translation of BMC to SAT and describe a BDD-based BMC for both LTL−X and ECTL−X. The two translations have been implemented, tested, and compared with each other on two standard benchmarks. Our experimental results reveal the advantages and disadvantages of both the approaches.
Soft Constraint Logic Programming and . . .
- Stefano Bistarelli; Ugo Montanari; Francesca Rossi
In this paper we study the relationship between Constraint Programming (CP) and Shortest Path (SP) problems. In particular, we show that classical, multicriteria, partially ordered, and modality-based SP problems can be naturally modeled and solved within the Soft Constraint Logic Programming (SCLP) framework, where logic programming is coupled with soft constraints. In this way we provide this large class of SP problems with a high-level and declarative linguistic support whose semantics takes care of both finding the cost of the shortest path(s) and also of actually finding the path(s). On the other hand, some efficient algorithms for certain classes of...
Semiring-based frameworks for trust . ..
- S. Bistarelli; S. N. Foley; B: O'Sullivan; F. Santini
Multitrust provides a flexible approach to encoding trust metrics whereby definitions for trust propagation and aggregation are specified in terms of a semiring. Determining the degree of trust between principals across a trust network is, in turn, programmed as a (semiring based) soft-constraint satisfaction problem. In this paper we consider the use of semiring-based metrics in reasoning about trust between coalition-forming principals. The configurable nature of multitrust makes it well-suited to modeling trust within coalitions: whether adding more principals to a coalition increases trust or decreases trust is captured by the definition of trust aggregation within the semiring.
A dynamic intelligent quality controller for cold rolling mill
- Cheng, Fei; He, Shan-Jun; Luo, Jian; IEEE; 罗键
Aimed at the problems of time varying parameters, strong nonlinearity, mutual interference, process disturbance and measurement noise in cold rolling mill (CRM) process, a new dynamic intelligent quality controller (DIQC) based on fuzzy logic and neural network was proposed for dealing with the question of AGC system. The structure and algorithm of DIQC were designed, and the method was employed in the control process of AGC in CRM. The experimental results show that the DIQC is more efficient and robust than the traditional PID controller. It is demonstrated that the DIQC has satisfactory dynamic performance.