| Testing Properties of Boolean Functions |
Jan 2012 |
165 pages |
| Authors:
Eric Blais; CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
|
 | Given oracle access to some boolean function f, how many queries do we need to test whether f is linear? Or monotone? Or whether its output is completely determined by a small number of the input variables? This thesis studies these and related questions in the framework of property testing introduced by Rubinfeld and Sudan ('96). The results of this thesis are grouped into three main lines of research. I. ... |
|
| Laced Boolean Functions and Subset Sum Problems in Finite Fields |
13 Mar 2011 |
18 pages |
| Authors:
David Canright; Sugata Gangopadhyay; Subhamoy Maitra; Pantelimon Stanica; NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF APPLIED MATHEMATICS
|
| In this paper, we investigate some algebraic and combinatorial properties of a special Boolean function on n variables, defined using weighted sums in the residue ring modulo the least prime p great n. We also give further evidence to a question raised by Shparlinski regarding this function, by computing accurately the Boolean sensitivity thus settling the question for prime number values p = n. Finally, we propose a generalization of ... |
|
| On a Combinatorial Conjecture |
Jan 2011 |
14 pages |
| Authors:
Thomas W Cusick; Yuan Li; Pantelimon Stanica; NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF APPLIED MATHEMATICS
|
| Recently, Tu and Deng proposed a combinatorial conjecture about binary strings and, on the assumption that the conjecture is correct, they obtained two classes of Boolean functions that are both algebraic immunity optimal, the first class of which are also bent functions. The second class gives balanced functions, which have optimal algebraic degree and the best nonlinearity known until now. In this paper, using three different approaches, we prove that ... |
|
| Bent Function Discovery by Reconfigurable Computer |
SEP 2010 |
13 pages |
| Authors:
Jon T. Butler; NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING
|
| Bent Boolean functions are important in the encoding/decoding of secure messages. Because they are the most nonlinear of all functions, they are the least susceptible to linear attack. However, bent functions are rare and difficult to discover. The only known way to enumerate all bent functions is by a sieve in which many prospective functions are tested. This is a tutorial description of the process of bent Boolean function discovery ... |
|
| Nonoverlap Property of the Thue-Morse Sequence |
20 Apr 2010 |
6 pages |
| Authors:
T W Cusick; P Stanica; NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF APPLIED MATHEMATICS
|
| In this note, we provide a new proof for the nonoverlap property of the Thue-Morse sequence using a Boolean functions approach. We also investigate other patterns that occur in a generalization of the Thue-Morse sequence. |
|
| Cube-Type Algebraic Attacks on Wireless Encryption Protocols |
Sep-2009 |
99 pages |
| Authors:
Nikolaos Petrakos; NAVAL POSTGRADUATE SCHOOL MONTEREY CA
|
| In this study, we investigated an algebraic-type attack, known as the cube attack, against wireless networks. We implemented the cube attack in a wireless system, namely Bluetooth. We formally modeled the encryption function of E0 Bluetooth key generator and automated the process of the cube attack on E0 of the factorization process (preprocessing phase). In this phase, an attacker finds as many maxterms (a term of the encryption function such ... |
|
| Gravitational and Magnetic Anomaly Inversion Using a Tree-Based Geometry Representation |
Jun-2009 |
24 pages |
| Authors:
George A Gazonas; Raymond A Wildman; ARMY RESEARCH LAB ABERDEEN PROVING GROUND MD WEAPONS AND MATERIALS RESEARCH DIRECTORATE
|
| Gravitational and magnetic anomaly inversion of homogeneous 2D and 3D structures is treated using a geometric parameterization that can represent multiple, arbitrary polygons or polyhedra and a local-optimization scheme based on a hill-climbing method. This geometry representation uses a tree data structure, which defines a set of Boolean operations performed on convex polygons. A variable-length list of points, whose convex hull defines a convex polygon operand, resides in each leaf ... |
|
| Sums of the Thue-Morse Sequence over Arithmetic Progressions |
29 May 2009 |
9 pages |
| Authors:
T W Cusick; P Stanica; NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF APPLIED MATHEMATICS
|
| In this note, we use the theory of Boolean functions to find a new elementary proof for Moser's conjecture that states that in the bounded sequence of nonnegative integers divisible by 3 there are more integers with an even number of 1s in their base-2 representation. This proof is simpler than the original proof by D. J. Newman in 1969. We further apply the method to prove a similar result ... |
|
| Verification using Satisfiability Checking, Predicate Abstraction, and Craig Interpolation |
Sep-2008 |
297 pages |
| Authors:
Himanshu Jain; CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
|
| Automatic verification of hardware and software implementations is crucial for computer systems. This thesis develops new techniques for building efficient decision procedures and adds new capabilities to existing decision procedures. Most SAT solvers require the input formula to be in Conjunctive Normal Form (CNF). However, typical formulas that arise in practice are not in CNF. Converting a general formula to CNF introduces overhead in the form of new variables and ... |
|
| Algorithms for White-box Obfuscation Using Randomized Subcircuit Selection and Replacement |
27-Mar-2008 |
99 pages |
| Authors:
Kenneth E Norman; AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH GRADUATE SCHOOL OF ENGINEERING AND MANAGEMENT
|
| Software protection remains an active research area with the goal of preventing adversarial software exploitation such as reverse engineering, tampering, and piracy. Heuristic obfuscation techniques lack strong theoretical underpinnings while current theoretical research highlights the impossibility of creating general, efficient, and information theoretically secure obfuscators. In this research, we consider a bridge between these two worlds by examining obfuscators based on the Random Program Model (RPM). Such a model envisions ... |
|
| Augmenting SAT Solvers for Network Configuration/Planning |
NOV 2006 |
7 pages |
| Authors:
Sharad Malik; PRINCETON UNIV NJ
|
| This project explored the possibility of alternate encodings of the planning problem and extensions to satisfiability (SAT) solvers that can better capture the constraints and objectives for network configurations. For example, the ability to directly deal with arithmetic constraints dealing with configuration cost, or probabilistic failure modes may lead to more compact encodings that are then dealt with more sophisticated decision procedures. The end goal is to capture the constraints ... |
|
| Certifying the Absence of Buffer Overflows |
SEP 2006 |
|
| Authors:
Sagar Chaki; Scott Hissam; CARNEGIE-MELLON UNIV PITTSBURGH PA SOFTWARE ENGINEERING INST
|
 | Despite increased awareness and efforts to reduce buffer overflows, they continue to be the cause of most software vulnerabilities. In large part, these problems are due to the widespread use of unsafe library routines among programmers. For reasons of efficiency, such routines will continue to be used, even during the development of mission-critical and safety-critical software systems. Effective certification techniques are needed to ascertain whether unsafe routines are used in ... |
|
| Privacy-Preserving Distributed Information Sharing |
JUL 2006 |
95 pages |
| Authors:
Lea Kissner; CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
|
| In many important applications, a collection of mutually distrustful parties must share information, without compromising their privacy. Currently, these applications are often performed by using some form of a trusted third party (TTP); this TTP receives all players inputs, computes the desired function, and returns the result. However, the level of trust that must be placed in such a TTP is often inadvisable, undesirable, or even illegal. In order to ... |
|
| Quantum Random Networks for Type 2 Quantum Computers |
09 JAN 2006 |
11 pages |
| Authors:
David L. Allara; Brosl Hasslacher; PENNSYLVANIA STATE UNIV UNIVERSITY PARK DEPT OF CHEMISTRY
|
| Random boolean networks (RBNs) have been studied theoretically and computationally in order to be able to use their remarkable self-healing and large basins of altercation properties as quantum computing architectures, especially focused on problems of physical interest which do not require universal computational structures. This preliminary study was limited primarily to ID strings, but eventually work should be directed beyond two state networks to multi-state ones. Available software was used ... |
|
| Berkeley's TREC 8 Interactive Track Entry: Cheshire II and Zprise |
2006 |
10 pages |
| Authors:
Ray R. Larson; CALIFORNIA UNIV BERKELEY SCHOOL OF INFORMATION MANAGEMENT AND SYSTEMS
|
| This paper briefly discusses the UC Berkeley entry in the TREC 8 Interactive Track. In this year's study twelve searchers conducted six searches each, half on the Cheshire II system and the other half on the Zprise system, for a total of 72 searches. Questionnaires were administered to each participant to gather information about basic demographic and searching experience, about each search, about each of the systems, and finally, about ... |
|
| A Partial Join Approach for Mining Co-Location Patterns: A Summary of Results |
29 DEC 2005 |
12 pages |
| Authors:
Jin S. Yoo; Shashi Shekhar; MINNESOTA UNIV MINNEAPOLIS DEPT OF COMPUTER SCIENCE
|
| Spatial co-location patterns represent the subsets of events whose instances are frequently located together in geographic space. The authors identified the computational bottleneck in the execution time of a current co-location mining algorithm. A large fraction of the join-based co-location miner algorithm is devoted to computing joins to identify instances of candidate co-location patterns. They propose a novel partial-join approach for mining co-location patterns efficiently. It transactionizes continuous spatial data ... |
|
| Polarization of Electromagnetic Radiation a Resource for Predicting Soil Moisture |
25 JUL 2005 |
4 pages |
| Authors:
Sam Nwaneri; Wubishet Tadasse; ALABAMA A AND M UNIV NORMAL DEPT OF PLANT AND SOIL SCIENCE
|
| This paper discusses the prediction model of soil moisture content (SMC). The purpose is to model SMC with respect to use segregation (useg), temperature, and the intensity of local solar radiation that causes polarization of electromagnetic radiation (EMR). The objectives include using basic laws of radiation to assess how radiation intimately interacts with matter. The methodology consists of four method spaces dealing with: polarization of dielectric medium; hysteresis accounting for ... |
|
| Automatic In-Flight Repair of FPGA Cosmic Ray Damage |
13 JUL 2005 |
15 pages |
| Authors:
Sarah Thompson; Alan Mycroft; Guillaume Brat; Arnaud Venet; NATIONAL AERONAUTICS AND SPACE ADMINISTRATION MOFFETT FIELD CA AMES RESEARCH CENTER
|
| FPGAs are finding an increasing number of applications within NASA in deep space probes, planetary rovers and manned vehicles. Like other silicon devices, FPGAs can be damaged by high energy cosmic ray impacts, resulting in permanent latch-up conditions that manifest as stuck-at faults. Traditionally, multiple redundancy and voting logic have been employed as a work-around, particularly for high reliability, extreme environment applications. However, reconfigurable FPGAs are becoming increasingly common in ... |
|
| Tools for User-Assisted Behavioral Monitoring of Distributed Information Networks |
JUN 2005 |
67 pages |
| Authors:
Kaliappa Ravindran; CITY COLL NEW YORK DEPT OF COMPUTER SCIENCE
|
| This research focused on providing an event specification approach to enable a flexible monitoring and control of distributed real-time information systems (DIS). The research constructed an object-oriented Application Programming Interface (API) that allows the monitoring of compliance to properties deemed as critical for function of a DIS. Users can prescribe critical properties in the form of event predicates, which are Boolean conditions on the externally visible computation state among the ... |
|
| Molecular Computation With Automated Microfluidic Sensors (MCAMS) |
AUG 2004 |
26 pages |
| Authors:
Laura Landweber; Lydia Sohn; Paul Alivasatos; TRUSTEES OF PRINCETON UNIV NEW JERSERY
|
| We combined microfluidic technology with recently developed algorithms of nucleic acid-based computing to demonstrate a compact, automated nucleotide-based computational device capable of rapid detection of computational output. We explored both experimental and theoretical aspects of the construction of microfluidic nucleic acid computing. Microreactors implementing Boolean operators lent themselves to a relatively simple implementation of DNA computing. On the theoretical side, we simulated the performance of individual reactors and designed small ... |
|
| Predicate Abstraction and Refinement Techniques for Verifying Verilog |
25 JUN 2004 |
27 pages |
| Authors:
Edmund Clarke; Himanshu Jain; Daniel Kroening; CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
|
| Model checking techniques applied to large industrial circuits suffer from the state explosion problem. A major technique to address this problem is abstraction. Predicate abstraction has been applied successfully to large software programs. Applying this technique to hardware designs poses additional challenges. This paper evaluates three techniques to improve the performance of SAT-based predicate abstraction of circuits: (1) We partition the abstraction problem by forming subsets of the predicates. The ... |
|
| Deciding Quantifier-Free Presburger Formulas using Finite Instantiation based on Parameterized Solution Bounds |
DEC 2003 |
20 pages |
| Authors:
Sanjit A. Seshia; Randal E. Bryant; CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
|
| Given a formula Phi in quantifier-free Presburger arithmetic, it is well known that, if there is a satisfying solution to Phi, there is one whose size, measured in bits, is polynomially bounded in the size of Phi. In this paper, we consider a special class of quantifier-free Presburger formulas in which most linear constraints are separation (difference-bound) constraints, and the non-separation constraints are sparse. This class has been observed to ... |
|
| Predicate Abstraction of ANSI-C Programs using SAT |
23 SEP 2003 |
26 pages |
| Authors:
Edmund Clarke; Daniel Kroening; Natasha Sharygina; Karen Yorav; CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
|
| Predicate abstraction is a major method for verification of software. However, the generation of the abstract Boolean program from the set of predicates and the original program suffers from an exponential number of theorem prover calls as well as from soundness issues. This paper presents a novel technique that uses an efficient SAT solver for generating the abstract transition relation of ANSI-C programs. The SATbased approach computes a more precise ... |
|
| Reflections on Logic & Probability in the Context of Conditionals |
Jul-2003 |
20 pages |
| Authors:
Philip G Calabrese; SPACE AND NAVAL WARFARE SYSTEMS CENTER SAN DIEGO CA
|
| This paper discusses various controversies surrounding the meaning and use of such conditionals as A given B or If B then A including that such Boolean fractions 1) can non-trivially carry the standard conditional probability, 2) are truth functional but with three rather than two truth values, 3) are logically and probabilistically non-monotonic, 4) can be combined with operations that extend the standard Boolean operations, and 5) allow definitions that ... |
|
| Accurate Boundary Evaluation and Interactive Display of Complex Datasets |
APR 2003 |
8 pages |
| Authors:
Dinesh Manocha; NORTH CAROLINA UNIV AT CHAPEL HILL DEPTOF COMPUTER SCIENCE
|
| We are addressing some fundamental research issues in modeling, display and simulation for computer-aided design and virtual environments. Our emphasis is to develop better algorithms and software systems and to demonstrate their applications. We are utilizing a number of techniques from algebraic geometry, approximation theory, computational geometry, numerical analysis, computer-aided geometric design and computer graphics to investigate the underlying mathematical concepts and to develop more efficient and robust geometric algorithms. ... |
|
| Temporal Abstraction in Bayesian Networks |
2003 |
7 pages |
| Authors:
Brendan Burns; Clayton T. Morrison; MASSACHUSETTS UNIV AMHERST DEPT OF COMPUTER SCIENCE
|
| A current popular approach to representing time in Bayesian belief networks is through Dynamic Bayesian Networks (DBNs) (Dean & Kanazawa, 1989). DBNs connect sequences of entire Bayes networks, each representing a situation at a snapshot in time. The authors present an alternative method for incorporating time into Bayesian belief networks that utilizes abstractions of temporal representations. This method maintains the principled Bayesian approach to reasoning under uncertainty, providing explicit representation ... |
|
| Design of a Millimeter Wave Data Link for a Radar Guided Missile |
SEP 2001 |
53 pages |
| Authors:
Larry J. Levitt; ARMY AVIATION AND MISSILE COMMAND REDSTONE ARSENAL AL
|
| This report describes a systems-level design of a data link that enables a high velocity missile to receive guidance commands from a 35 GHzRadar. The objectives for this design include a Bit Error Rate (BER) of 10-6 at 1 km downrange, low power consumption, and miniaturized components so that the data link can fit on the back of a missile. No custom designed electronic chips are necessary. The design assumes ... |
|
| Saturation: An Efficient Iteration Strategy for Symbolic State-space Generation |
FEB 2001 |
18 pages |
| Authors:
Gianfranco Ciardo; Gerald Luttgen; Radu Siminiceanu; INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA
|
| This paper presents a novel algorithm for generating state spaces of asynchronous systems using Multi?valued Decision Diagrams. In contrast to related work, the next?state function of a system is not encoded as a single Boolean function, but as cross?products of integer functions. This permits the application of various iteration strategies to build a system's state space. In particular, this paper introduces a new elegant strategy, called saturation, and implements it ... |
|
| Adding Boolean-Quality Control to Best-Match Searching via an Improved User Interface |
01 MAY 2000 |
31 pages |
| Authors:
Donald Byrd; Rodion Podorozhny; MASSACHUSETTS UNIV AMHERST CENTER FOR INTELLIGENT INFORMATION RETRIEVAL
|
| While end users these days seem happy with best-match text-retrieval systems, it appears that expert searchers still prefer exact-match (Boolean) text-retrieval systems by an overwhelming margin. This is somewhat surprising. Most expert searchers were probably trained with Boolean systems, and an obvious factor is simply preferring the familiar, but we argue that a second major factor is that these experts feel a much greater sense of control with Boolean than ... |
|
| A Typed and Temporal Object-Oriented Technology |
OCT 1999 |
7 pages |
| Authors:
Suad Alagic; WICHITA STATE UNIV KS
|
| A typed and temporal object oriented paradigm has been developed. A declarative object oriented, temporal constraint language MyT, its type system, and a model of persistence have been designed. The results on the associated model theory based on order sorted algebras and the view of MyT classes as temporal theories have been established. A provably type safe technique called constrained matching has been developed for ... |
|
| Formal Representation and Application of Software Design Information |
SEP 1999 |
288 pages |
| Authors:
Thomas M. Schorsch; AIR FORCE INST OF TECH WRIGHT-PATTERSONAFB OH SCHOOL OF ENGINEERING
|
| Formal methods for developing software use mathematical frameworks to specify, develop and verify software systems, especially safety critical systems where error free software is a necessity. A transformation system is a formal method that refines a requirement specification into an implementation by successively adding design decisions in the form of precisely verified design information. Current algebraic representations of design information (specifications, morphisms, and interpretations) and methods for applying algebraic specification ... |
|
| Processor Verification Using Efficient Reductions of the Logic of Uninterpreted Functions to Propositional Logic |
MAY 1999 |
47 pages |
| Authors:
Randal E. Bryant; Steven German; Miroslav N. Velev; CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
|
| The logic of equality with uninterpreted functions (EUF) provides a means of abstracting the manipulation of data by a processor when verifying the correctness of its control logic. By reducing formulas in this logic to propositional formulas, we can apply Boolean methods such as Ordered Binary Decision Diagrams (BDDs) and Boolean satisfiability checkers to perform the verification. We can exploit characteristics of the formulas describing the verification conditions to greatly ... |
|
| Symbolic Model Checking without BDDs |
04 JAN 1999 |
20 pages |
| Authors:
Armin Biere; Alessandro Cimatti; Edmund Clark; Yunshan Zhu; CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
|
| Symbolic Model Checking has proven to be a powerful technique for the verification of reactive systems. BDDs have traditionally been used as a symbolic representation of the system. In this paper we show how boolean decision procedures, like Stillmarck's Method or the Davis and Putnam Procedure, can replace BDDs. This new technique avoids the space blow up of BDDs, generates counterexamples much faster, and sometimes speeds up the ... |
|
| Approximate Symbolic Model Checking Using Overlapping Projections |
1999 |
9 pages |
| Authors:
Shankar G. Govindaraju; David L. Dill; STANFORD UNIV CA COMPUTER SYSTEMS LAB
|
| Abstract Symbolic Model Checking extends the scope of verification algorithms that can be handled automatically, by using symbolic representations rather than explicitly searching the entire state space of the model. However even the most sophisticated symbolic methods cannot be directly applied to many of today's large designs because of the state explosion problem. Approximate symbolic model checking is an attempt to trade off accuracy with the capacity to deal with ... |
|
| Proliferation Path Assessment and Targeting System (PPATS) |
OCT 1998 |
64 pages |
| Authors:
Richard L. Walker; Thea E. Kreinik; Ronald V. Roman; BDM INTERNATIONAL INC MCLEAN VA
|
| The Proliferation Path Assessment and Targeting System (PPATS) provides a common framework for conducting counterproliferation analysis. PPATS displays a network of acquisition pathways for nuclear, chemical and biological (NBC) weapons of mass destruction (WMD). The network display can be expanded to reveal individual process steps involving activities, equipment and materials. The PPATS software allows its users to link intelligence to the process steps, ascertain evidence of activity at certain steps ... |
|
| Learning Evaluation Functions for Global Optimization |
01 AUG 1998 |
217 pages |
| Authors:
Justin Andrew Boyan; CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
|
| In complex sequential decision problems such as scheduling factory production, planning medical treatments, and playing backgammon, optimal decision policies are in general unknown, and it is often difficult, even for human domain experts, to manually encode good decision policies in software. The reinforcement learning methodology of value function approximation (VFA) offers an alternative: systems can learn effective decision policies autonomously, simply by simulating the task ... |
|
| Ordered Binary Decision Diagrams and Minimal Trellises |
30 JUL 1998 |
36 pages |
| Authors:
John Lafferty; Alexander Vardy; CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
|
| Ordered binary decision diagrams (OBDDs) are graph based data structures for representing Boolean functions. They have found widespread use in computer aided design and in formal verification of digital circuits. Minimal trellises are graphical representations of error correcting codes that play a prominent role in coding theory. This paper establishes a close connection between these two graphical models, as follows. Let C be a binary code ... |
|
| Classical Combinatorial Sequential Machine Components Implemented with Quantum Devices |
MAY 1998 |
36 pages |
| Authors:
Daniel J. Pease; SYRACUSE UNIV NY OFFICE OF SPONSORED PROGRAMS
|
| The majority of work today relating to quantum computing has provided results that are almost incomprehensible to even the most advanced computer architect. This paper uses the recent research results of quantum mechanical logic as building blocks to derive a computer architecture based on quantum devices that is consistent with existing system architectures. The new and admittedly exotic nature of quantum computing notwithstanding, this work presents a quantum mechanical analog ... |
|
| Arithmetic Circuit Verification Based on Word-Level Decision Diagrams |
MAY 1998 |
127 pages |
| Authors:
Yirng-An Chen; CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
|
| The division bug in Intel's Pentium processor has demonstrated the importance and the difficulty of verifying arithmetic circuits and the high cost of an arithmetic bug. In this thesis, we develop verification methodologies and symbolic representations for functions mapping Boolean vectors to integer or floating-point values, and build verification systems for arithmetic circuits. Our first approach is based on a hierarchical methodology and uses ... |
|
| Synthesis of ESI Equivalence Class Combinational Circuit Mutants |
OCT 1997 |
11 pages |
| Authors:
J. Harlow; F. Brglez; NORTH CAROLINA STATE UNIV AT RALEIGH DEPT OF COMPUTER SCIENCE
|
| Despite more than a decade of experience with the use of standardized benchmark circuits, meaningful comparisons of EDA algorithms remain elusive. In this paper, we introduce an entirely new methodology for characterizing the performance of Binary Decision Diagram (BDD) software. Our method involves the synthesis of large equivalence classes of Entropy Signature Invariant (ESI) circuits, based on a known reference circuit. We demonstrate that such classes induce controllable distributions of ... |
|
| On Proof Realization of Intuitionistic Logic |
OCT 1997 |
20 pages |
| Authors:
S. N. Artemov; CALIFORNIA UNIV BERKELEY
|
| In 1933 Godel Introduced an axiomatic system, currently known as S4, for a logic of an absolute provability. The problem of finding a fair probability model for S4 was left open. In the current paper we demonstrate how the Intuitionistic propositional logic Int can be directly realized by proof polynomials. It is shown that Int is complete with respect to this proof realizability. |
|
| Hybrid Spectral Transform Diagrams |
04 JUN 97 |
|
| Authors:
E. M. Clarke; M. Fujita; W. Heinle; CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
|
| We give a uniform algebraic framework for computing hybrid spectral transforms in an efficient manner. Based on properties of the Kronecker product, we derive a set of recursive equations, which leads naturally to an algorithm for computing such transforms efficiently. As a result, many applications of transforms like the Walsh transform and the Reed-Muller transform, which were previously impossible because of memory constraints, have now become feasible. The same set ... |
|
| PBHD: An Efficient Graph Representation for Floating Point Circuit Verification |
MAY 1997 |
|
| Authors:
Yirng-An Chen; Randal E. Bryant; CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
|
| *BMDs, HDDs, and K*BMDs provide compact representations for functions which map Boolean vectors into integer values, but not floating point values. In this paper, we propose a new data structure, called Multiplicative Power Binary Hybrid Diagrams (*PBHDs), to provide a compact representation for functions that map Boolean vectors into integer or floating point values. The size of the graph to represent the IEEE floating point encoding is linear with the ... |
|
| Complexity of Algorithms for Problems in Proposition Logic |
APR 97 |
39 pages |
| Authors:
John Franco; John Schlipf; CINCINNATI UNIV OH
|
| Our work under ONR sponsorship has produced results illuminating the nature of certain well-known polynomial time subclasses of Satisfiability. Most of these classes are interesting because they have arisen from consideration of Linear Programming concepts to formulations of Satisfiability. We have also achieved progress in the related area of the well-founded semantics for logic programming. |
|
| Breadth-First with Depth-First BDD Construction: A Hybrid Approach |
MAR 97 |
|
| Authors:
Yirng-An Chen; Bwolen Yang; Randal E. Bryant; CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
|
| This paper presents the technique of operator sifting as a new way of understanding both breadth-first and depth-first approaches to BDD construction. A new algorithm is also proposed to capture the breadth-first approach's advantage of memory access locality, while keeping the depth-first approach's advantage of low memory overhead. Our preliminary experimental results show that our approach is generally faster than other implementations that rely exclusively on either breadth-first or depth-first ... |
|
| Languages, Behaviors, Hybrid Architectures and Motion Control |
1997 |
30 pages |
| Authors:
Vikram Manikonda; P. S. Krishnaprasad; James Hendler; MARYLAND UNIV COLLEGE PARK INST FOR SYSTEMS RESEARCH
|
| In this paper, the authors put forth a framework that integrates features of reactive planning models with modern control-theory-based approaches to motion control of robots. They introduce a motion description language, MDLe, that provides a formal basis for robot programming using behaviors, and at the same time permits incorporation of kinematic and dynamic models of robots given in the form of differential equations. In particular, behaviors for robots are formalized ... |
|
| Algebraic Algorithm Design and Local Search |
DEC 96 |
387 pages |
| Authors:
Robert P. Graham Jr; AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH
|
| Formal, mathematically-based techniques promise to play an expanding role in the development and maintenance of the software on which our technological society depends. Algebraic techniques have been applied successfully to algorithm synthesis by the use of algorithm theories and design tactics, an approach pioneered in the Kestrel Interactive Development System (KIDS). An algorithm theory formally characterizes the essential components of a family of algorithms. A design tactic is a specialized ... |
|
| Optimization and Artificial Intelligence |
22 JUL 96 |
22 pages |
| Authors:
E. Boros; P. L. Hammer; F. S. Roberts; RUTGERS - THE STATE UNIV NEW BRUNSWICK NJ
|
| We propose to do research in a number of areas at the interface between operations research and artificial intelligence: pattern finding and sequential diagnosis, managing data and knowledge bases efficiently, and scheduling problems. |
|
| Logical/Linear Operators in Early Vision |
14 JUN 96 |
23 pages |
| Authors:
Steven W. Zucker; MCGILL UNIV MONTREAL (QUEBEC)
|
| We propose a research program to investigate new techniques for computing image descriptions in early vision. The program will incorporate computational, physiological and psychophysical aspects. Research will be focused on the certain non-linearities that we have discovered can play an important role in improving the robustness of edge, line, and curve detection. These non-linearities are totally different from those previously studied in early vision. We embody them in what we ... |
|
| Workshop on Satisfiability Siena, Italy on 28 April - 3 May 1996 |
MAY 96 |
35 pages |
| Authors:
John Franco; Giogio Gallo; Hans K. Buening; Ewald Speckenmeyer; Cosimo Spera; CINCINNATI UNIV OH
|
| Partial contents include : (1) 0-1 Threshold for random constant- width formulas; (2) Lagrangian methods; (3) Probabilistic analysis of Davis- Putnam variants; (4) Fixed-parameter-tractable hierarchies of SAT classes; (5) Upper bounds on the complexity of 3-satisfiability; (6) Resolution proof length; (7) Polynomial time solvable subclasses of satisfiability; (8) Partially defined Boolean functions, and (9) Multispace search. |
|
Reports by Keyword(s)
BOOLEAN ALGEBRA
