Search

We prove the first unconditional consistency result for superpolynomial circuit lower bounds with a relatively strong theory of bounded arithmetic. Namely, we show that the theory ‍V20 is consistent with the conjecture that ‍NEXP ‍⊈ ‍P/poly, i.e., some problem that is solvable in non-deterministic exponential time does not have polynomial size circuits. We suggest this is the best currently available evidence for the truth of the conjecture. Additionally, we establish a magnification result on the hardness of proving circuit lower bounds., Albert Atserias: Supported in part by Project PID2019-109137GB-C22 (PROOFS) and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M) of the Spanish State Research Agency. Sam Buss: Supported in part by Simons Foundation grant 578919., Peer Reviewed, Postprint (author's final draft)

MaxSAT, the optimization version of the well-known SAT problem, has attracted a lot of research interest in the past decade. Motivated by the many important applications and inspired by the success of modern SAT solvers, researchers have developed many MaxSAT solvers. Since most research is algorithmic, its significance is mostly evaluated empirically. In this paper, we want to address MaxSAT from the more formal point of view of proof complexity. With that aim, we start providing basic definitions and proving some basic results. Then we analyse the effect of adding split and virtual, two original inference rules, to MaxSAT resolution. We show that each addition makes the resulting proof system stronger, even when virtual is restricted to empty clauses (0-virtual). We also analyse the power of our proof systems in the particular case of SAT refutations. We show that our strongest system, ResSV, is equivalent to circular and dual rail with split. We also analyse empirically some known gadget-based reformulations. Our results seem to indicate that the advantage of these three seemingly different systems over general resolution comes mainly from their ability of augmenting the original formula with hypothetical inconsistencies, as captured in a very simple way by the virtual rule., Under project RTI2018-094403-B-C33 funded by MCIN/AEI/ 10.13039/501100011033 and FEDER ”Una manera de hacer Europa", Peer Reviewed, Postprint (author's final draft)

We study a natural variant of the implicational fragment of propositional logic. Its formulas are pairs of conjunctions of positive literals, related together by an implicational-like connective; the semantics of this sort of implication is defined in terms of a threshold on a conditional probability of the consequent, given the antecedent: we are dealing with what the data analysis community calls confidence of partial implications or association rules. Existing studies of redundancy among these partial implications have characterized so far only entailment from one premise and entailment from two premises, both in the stand-alone case and in the case of presence of additional classical implications (this is what we call "relative entailment"). By exploiting a previously noted alternative view of the entailment in terms of linear programming duality, we characterize exactly the cases of entailment from arbitrary numbers of premises, again both in the stand-alone case and in the case of presence of additional classical implications. As a result, we obtain decision algorithms of better complexity; additionally, for each potential case of entailment, we identify a critical confidence threshold and show that it is, actually, intrinsic to each set of premises and antecedent of the conclusion., Peer Reviewed, Postprint (published version)

We extend the termination proof methods based on reduction orderings to higher-order rewriting systems based on higher-order pattern matching. We accommodate, on the one hand, a weakly polymorphic, algebraic extension of Church's simply typed λ-calculus and, on the other hand, any use of eta, as a reduction, as an expansion, or as an equation. The user's rules may be of any type in this type system, either a base, functional, or weakly polymorphic type., Peer Reviewed, Postprint (author's final draft)

Mobile apps bring unprecedented levels of convenience, yet they are often buggy, and their bugs offset the convenience the apps bring. A key reason for buggy apps is that they must handle a vast variety of system and user actions such as being randomly killed by the OS to save resources, but app developers, facing tough competitions, lack time to thoroughly test these actions. AppDoctor is a system for efficiently and effectively testing apps against many system and user actions, and helping developers diagnose the resultant bug reports. It quickly screens for potential bugs using approximate execution, which runs much faster than real execution and exposes bugs but may cause false positives. From the reports, AppDoctor automatically verifies most bugs and prunes most false positives, greatly saving manual inspection effort. It uses action slicing to further speed up bug diagnosis. We implement AppDoctor in Android. It operates as a cloud of physical devices or emulators to scale up testing. Evaluation on 53 out of 100 most popular apps in Google Play and 11 of the most popular open-source apps shows that, AppDoctor effectively detects 72 bugs--including two bugs in the Android framework that affect all apps--with quick checking sessions, speeds up testing by 13.3 times and vastly reduces diagnosis effort., Presented at EuroSys 2014, held in Amsterdam, Netherlands, 13-16 April 2014. Sponsored in part by Air Force Research Laboratory grant no. FA8750-10-2-0253 and the Office of Naval Research grant no. N00014-12-1-0166

This report identifies a candidate architecture for an energy efficient SFQ-based processor unit. It quantitatively analyzes candidates for register and main memory with respect to access time, density and energy efficiency. Finally, it investigates the efficacy of three dimensional integration (3DI) for enhancing aerial circuit density., The original document contains color images.

The use of shared mutable state, commonly seen in object-oriented systems, is often problematic due to the potential conflicting interactions between aliases to the same state. We present a substructural type system outfitted with a novel lightweight interference control mechanism, rely-guarantee protocols, that enables controlled aliasing of shared resources. By assigning each alias separate roles, encoded in a novel protocol abstraction in the spirit of rely-guarantee reasoning our type system ensures that challenging uses of shared state will never interfere in an unsafe fashion. In particular, rely-guarantee protocols ensure that each alias will never observe an unexpected value, or type, when inspecting shared memory regardless of how the changes to that shared state (originating from potentially unknown program contexts) are interleaved at run-time., This document is a companion technical report of the paper, Rely-Guarantee Protocols , to appear in the Proceedings of the European Conference on Object-Oriented Programming (ECOOP) 2014. It includes the complete technical development, detailed proofs, and additional examples that are not in the ECOOP paper.

A strong physically unclonable function (PUF) is a circuit structure that extracts an exponential number of unique chip signatures from a bounded number of circuit components. The strong PUF unique signatures can enable a variety of low-overhead security and intellectual property protection protocols applicable to several computing platforms. This paper proposes a novel lightweight (low overhead) strong PUF based on the timings of a classic processor architecture. A small amount of circuitry is added to the processor for on the-fly extraction of the unique timing signatures. To achieve desirable strong PUF properties, we develop an algorithm which leverages intentional post-silicon aging to tune the interchip and intra-chip signature variation. Our evaluation results show that the new PUF meets the desirable inter- and intrachip strong PUF characteristics, while its overhead is much lower than the existing strong PUFs. For the processors implemented in 45nm technology, the average inter-chip Hamming distance for 32-bit responses is increased by 16.1% after applying our post-silicon tuning method; the aging algorithm also decreases the average intra-chip Hamming distance by 98.1% (for 32-bit responses., Final version published in Emerging Topics in Computing, v2 n1 p16-29, March 2014; IEEE may assert copyright.

Technological advances over the past decade have enabled scientists to create ever larger and more complex scientific data sets. The main challenge in Scientific Visualization is mapping high-dimensional data onto a 2D display with only 3 perceptual dimensions (RGB colors). In this research we propose and evaluate methods for creating and combining textures for multi-field visualization. We have identified four classes of post-processing techniques for combining textural representations of field data: blending, overlay, bump mapping, and masking. We evaluated the effectiveness of these methods by using them for visualizing multiple vector fields using Line Integral Convolution (LIC) textures. Our user study suggests that blending is the most effective technique to combine multiple vector field visualization textures, while masking performs worst. There is some evidence that visualizations with smooth color changes are perceived as visually more attractive, and that aesthetics increases the perceived effectiveness of a visualization technique. Based on these results we have created a new generative formal grammar called texture grammar that combines implementations of existing visualization techniques and image compositing techniques to automatically produce visualizations, depending on the input fields., Includes Chris van Egmond, Charl Botha, Burkhard C. Wurnsche. Design and Evaluation of Multifield Visualisation Techniques for 2D Vector Fields, Proceedings of the 27th International Image and Vision Computing New Zealand Conference (IVCNZ 2012), 26 - 28 November 2012, Dunedin, New Zealand, pp. 115-120. The original document contains color images.

Reasoning about complex networks has in recent years become an important topic of study due to its many applications: the adoption of commercial products, spread of disease, the diffusion of an idea, etc. In this paper, we present the MANCaLog language, a formalism based on logic programming that satisfies a set of desiderata proposed in previous work as recommendations for the development of approaches to reasoning in complex networks. To the best of our knowledge, this is the first formalism that satisfies all such criteria. We first focus on algorithms for finding minimal models (on which multi-attribute analysis can be done), and then on how this formalism can be applied in certain real world scenarios. Towards this end, we study the problem of deciding group membership in social networks: given a social network and a set of groups where group membership of only some of the individuals in the network is known, we wish to determine a degree of membership for the remaining group-individual pairs. We develop a prototype implementation that we use to obtain experimental results on two real world datasets, including a current social network of criminal gangs in a major U.S. city. We then show how the assignment of degree of membership to nodes in this case allows for a better understanding of the criminal gang problem when combined with other social network mining techniques including detection of sub-groups and identification of core group memberswhich would not be possible without further identification of additional group members.

The modeling of cascade processes in multi-agent systems in the form of complex networks has in recent years become an important topic of study due to its many applications: the adoption of commercial products, spread of disease, the diffusion of an idea, etc. In this paper, we begin by identifying a desiderata of seven properties that a framework for modeling such processes should satisfy: the ability to represent attributes of both nodes and edges, an explicit representation of time, the ability to represent non-Markovian temporal relationships, representation of uncertain information, the ability to represent competing cascades, allowance of non-monotonic diffusion, and computational tractability. We then present the MANCaLog language, a formalism based on logic programming that satisfies all these desiderata, and focus on algorithms for finding minimal models (from which the outcome of cascades can be obtained) as well as how this formalism can be applied in real world scenarios. We are not aware of any other formalism in the literature that meets all of the above requirements., The original document contains color images. This is an extended version of MANCaLog: A Logic for Multi-Attribute Network Cascades, which appears in: Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013), Ito, Jonker, Gini, and Shehory (eds.), Held May 6-10, 2013 in Saint Paul, Minnesota, USA.

Several real world tasks involve data that is uncertain and relational in nature. Traditional approaches like first-order logic and probabilistic models either deal with structured data or uncertainty, but not both. To address these limitations, statistical relational learning (SRL), a new area in machine learning integrating both first-order logic and probabilistic graphical models, has emerged in the recent past. The advantage of SRL models is that they can handle both uncertainty and structured/ relational data. As a result, they are widely used in domains like social network analysis, biological data analysis, and natural language processing. Bayesian Logic Programs (BLPs), which integrate both first-order logic and Bayesian networks are a powerful SRL formalism developed in the recent past. In this dissertation, we develop approaches using BLPs to solve two real world tasks plan recognition and machine reading., Supported in part by USAF.

A logical framework and its implementation should serve as a flexible tool for specifying, simulating, and reasoning about formal systems. When the formal systems we are interested in exhibit state and concurrency, however, existing logical frameworks fall short of this goal. Logical frameworks based on a rewriting interpretation of substructural logics, ordered and linear logic in particular, can help. To this end, this dissertation introduces and demonstrates four methodologies for developing and using substructural logical frameworks for specifying and reasoning about stateful and concurrent systems. Structural focalization is a synthesis of ideas from Andreoli's focused sequent calculi and Watkins's hereditary substitution. We can use structural focalization to take a logic and define a restricted form of derivations, the focused derivations, that form the basis of a logical framework. We apply this methodology to define SLS, a logical framework for substructural logical specifications, as a fragment of ordered linear lax logic. Logical correspondence is a methodology for relating and inter-deriving different styles of programming language specification in SLS. The styles we connect range from very high-level specification styles like natural semantics, which do not fully specify the control structure of programs, to low-level specification styles like destination-passing, which provide detailed control over concurrency and control flow. We apply this methodology to systematically synthesize a low-level destination-passing semantics for a Mini-ML language extended with stateful and concurrent primitives. The specification is mostly high-level except for the relatively few rules that actually deal with concurrency. Linear logical approximation is a methodology for deriving program analyses by performing abstract analysis on the SLS encoding of the language's operational semantics.

This effort explored research and development, and deployment opportunities in the emerging disciplines of nanoscience, nanoengineering, and nanobioscience, for advanced computing architectures. The effort consisted of a multiyear, multidisciplinary effort focusing on research and development of nanocomputers systems utilizing alternative nanotechnology processing approaches that can deliver revolutionary computational capabilities crucial to maintaining technological progress. This research involved both modeling and simulations, as well as fabrication and test of prototype nanocomputing systems. Modeling results were regularly compared with experimental data as a validity check, and results were published in refereed journals and conferences., The original document contains color images.

The goal of this project is to develop theoretical frameworks and computational tools for synthesis of provably correct control and communication strategies for teams of autonomous vehicles from specifications given in rich, human-like language. Central to our approach are finite abstractions, which allow for the use of (adapted) temporal logics as specification languages, tools from formal verification resembling model checking for analysis and control, and techniques inspired from synchronization in concurrency theory for synthesis of communication strategies. We believe that we accomplished the initial objectives of the project. Specifically, we developed abstraction and control strategy for discrete-time affine systems, techniques for MDP control from PLTL and PCTL formulas, a top-down approach for distributed synthesis of control and communication strategies, and several applications to robot motion planning and control., The original document contains color images.

This project has developed a theoretical framework for describing and reasoning about changes in software. The theory provides a basis for the implementation of tools to support software maintenance tasks in the presence of changes. Specific contributions include the choice calculus, a formalism for representing variation and changes in structured documents. The choice calculus offers laws and transformation rules that make variation representations flexible. A design theory for the choice calculus has been developed for the systematic elimination of redundancies or dead variants. Another focus of this project has been the development of methods for effectively checking properties of variational software, which has led to the design of variational type systems and new unification algorithms. The practical work with variational software is supported through a user study that has demonstrated that the dimension-structured choice constructs of the choice calculus help users reason about variational code faster and more accurately and ultimately support code understanding better than traditional CPP annotations. Finally, a domain-specific language (DSL) has been developed which makes it possible to write programs to query, manipulate, and analyze variation structures., The original document contains color images.

In recent years there has been interest in achieving application level consistency criteria without the latency and availability costs of strongly consistent storage infrastructure. A standard technique is to adopt a vocabulary of commutative operations this avoids the risk of inconsistency due to message reordering. A more powerful approach was recently captured by the CALM theorem, which proves that logically monotonic programs are guaranteed to be eventually consistent. In logic languages such as Bloom, CALM analysis can automatically verify that program modules achieve consistency without coordination. In this paper we present BloomL, an extension to Bloom that takes inspiration from both these traditions. BloomL generalizes Bloom to support lattices and extends the power of CALM analysis to whole programs containing arbitrary lattices. We show how the Bloom interpreter can be generalized to support efficient evaluation of lattice-based code using well-known strategies from logic programming. Finally we use BloomL to develop several practical distributed programs including a key-value store similar to Amazon Dynamo and show how BloomL encourages the safe composition of small, easy-to-analyze lattices into larger programs.

With the industry-wide shift to multi-core processors and the rise of large-scale clusters as the engines for web services, it is clear that the future is all about exploiting parallelism. Unfortunately, writing parallel or concurrent software has long been a notoriously difficult task for programmers. In particular, the goals of maintaining correctness while also achieving high performance are far more challenging in a parallel or concurrent environment compared with a single-threaded system. Meld is a logic-based programming language that has proven effective for programming massively distributed systems. In this report, we describe Meld and how it can also be used to program more traditional parallel machines. We evaluate Meld on a small set of benchmarks and describe some of the methods we use to make it an effective tool for parallel programming. While more work needs to be done, it is clear that the use of a single language for describing both computation and coordination can lead to clear, concise, and efficient implementations., The original document contains color images.

Recently, researchers have been interested in reversible computing because of its ability to dissipate nearly zero heat and because of its applications in quantum computing and low power VLSI design. Synthesis and testing are two important areas of reversible logic. The thesis first presents an approach for the synthesis of reversible circuits from the exclusive- OR sum-of-products (ESOP) representation of functions, which makes better use of shared functionality among multiple outputs, resulting in up to 75% minimization of quantum cost compared to the previous approach. This thesis also investigates the previous work on constructing the online testable circuits and points out some design issues. A simple approach for online fault detection is proposed for a particular type of ESOP-based reversible circuit, which is also extended for any type of Toffoli circuits. The proposed online testable designs not only address the problems of the previous designs but also achieve significant improvements of up to 78% and 99% in terms of quantum cost and garbage outputs, respectively.

Recently, researchers have been interested in reversible computing because of its ability to dissipate nearly zero heat and because of its applications in quantum computing and low power VLSI design. Synthesis and testing are two important areas of reversible logic. The thesis first presents an approach for the synthesis of reversible circuits from the exclusive- OR sum-of-products (ESOP) representation of functions, which makes better use of shared functionality among multiple outputs, resulting in up to 75% minimization of quantum cost compared to the previous approach. This thesis also investigates the previous work on constructing the online testable circuits and points out some design issues. A simple approach for online fault detection is proposed for a particular type of ESOP-based reversible circuit, which is also extended for any type of Toffoli circuits. The proposed online testable designs not only address the problems of the previous designs but also achieve significant improvements of up to 78% and 99% in terms of quantum cost and garbage outputs, respectively.

Recently, researchers have been interested in reversible computing because of its ability to dissipate nearly zero heat and because of its applications in quantum computing and low power VLSI design. Synthesis and testing are two important areas of reversible logic. The thesis first presents an approach for the synthesis of reversible circuits from the exclusive- OR sum-of-products (ESOP) representation of functions, which makes better use of shared functionality among multiple outputs, resulting in up to 75% minimization of quantum cost compared to the previous approach. This thesis also investigates the previous work on constructing the online testable circuits and points out some design issues. A simple approach for online fault detection is proposed for a particular type of ESOP-based reversible circuit, which is also extended for any type of Toffoli circuits. The proposed online testable designs not only address the problems of the previous designs but also achieve significant improvements of up to 78% and 99% in terms of quantum cost and garbage outputs, respectively.

Recently, researchers have been interested in reversible computing because of its ability to dissipate nearly zero heat and because of its applications in quantum computing and low power VLSI design. Synthesis and testing are two important areas of reversible logic. The thesis first presents an approach for the synthesis of reversible circuits from the exclusive- OR sum-of-products (ESOP) representation of functions, which makes better use of shared functionality among multiple outputs, resulting in up to 75% minimization of quantum cost compared to the previous approach. This thesis also investigates the previous work on constructing the online testable circuits and points out some design issues. A simple approach for online fault detection is proposed for a particular type of ESOP-based reversible circuit, which is also extended for any type of Toffoli circuits. The proposed online testable designs not only address the problems of the previous designs but also achieve significant improvements of up to 78% and 99% in terms of quantum cost and garbage outputs, respectively.

Recently, researchers have been interested in reversible computing because of its ability to dissipate nearly zero heat and because of its applications in quantum computing and low power VLSI design. Synthesis and testing are two important areas of reversible logic. The thesis first presents an approach for the synthesis of reversible circuits from the exclusive- OR sum-of-products (ESOP) representation of functions, which makes better use of shared functionality among multiple outputs, resulting in up to 75% minimization of quantum cost compared to the previous approach. This thesis also investigates the previous work on constructing the online testable circuits and points out some design issues. A simple approach for online fault detection is proposed for a particular type of ESOP-based reversible circuit, which is also extended for any type of Toffoli circuits. The proposed online testable designs not only address the problems of the previous designs but also achieve significant improvements of up to 78% and 99% in terms of quantum cost and garbage outputs, respectively.

This thesis presents an approach to image classification via a Multi-Layer Perceptron (MLP) Artificial Neural Network (ANN) on the SRC-6 reconfigurable computer for use in classifying Low Probability of Intercept (LPI) radar emitters. The rationale behind the previously unexplored use of new reconfigurable computers combined with neural networks for this application is the potential for near real-time classification. Current potential near-peer competitors have access to LPI technology, so development of quick classification methods is crucial for ships to determine intent and to enable the possibility for self-defense against these types of emitters. The neural network, based on work conducted by Professor Phillip E. Pace of the Naval Postgraduate School (NPS), generates integer-cast weights by first using a sequential processor to conduct floating-point backpropagation to train the network on potential timefrequency images that allows generation of weights with lower overall Root Mean Squared (RMS) errors. The weights are then used in a parallel-processing reconfigurable computer for close to real-time classification. A second method of direct pixel comparison using Exclusive-Or (XOR) logic is presented as an alternative image classification method. Comparisons to similar representations in C++ are provided, for use in judging comparative error levels and timing between parallel and sequential processing methods., http://archive.org/details/neuralnetworkdes109452396, Approved for public release; distribution is unlimited.

Recently, researchers have been interested in reversible computing because of its ability to dissipate nearly zero heat and because of its applications in quantum computing and low power VLSI design. Synthesis and testing are two important areas of reversible logic. The thesis first presents an approach for the synthesis of reversible circuits from the exclusive- OR sum-of-products (ESOP) representation of functions, which makes better use of shared functionality among multiple outputs, resulting in up to 75% minimization of quantum cost compared to the previous approach. This thesis also investigates the previous work on constructing the online testable circuits and points out some design issues. A simple approach for online fault detection is proposed for a particular type of ESOP-based reversible circuit, which is also extended for any type of Toffoli circuits. The proposed online testable designs not only address the problems of the previous designs but also achieve significant improvements of up to 78% and 99% in terms of quantum cost and garbage outputs, respectively.

Recently, researchers have been interested in reversible computing because of its ability to dissipate nearly zero heat and because of its applications in quantum computing and low power VLSI design. Synthesis and testing are two important areas of reversible logic. The thesis first presents an approach for the synthesis of reversible circuits from the exclusive- OR sum-of-products (ESOP) representation of functions, which makes better use of shared functionality among multiple outputs, resulting in up to 75% minimization of quantum cost compared to the previous approach. This thesis also investigates the previous work on constructing the online testable circuits and points out some design issues. A simple approach for online fault detection is proposed for a particular type of ESOP-based reversible circuit, which is also extended for any type of Toffoli circuits. The proposed online testable designs not only address the problems of the previous designs but also achieve significant improvements of up to 78% and 99% in terms of quantum cost and garbage outputs, respectively.

Recently, researchers have been interested in reversible computing because of its ability to dissipate nearly zero heat and because of its applications in quantum computing and low power VLSI design. Synthesis and testing are two important areas of reversible logic. The thesis first presents an approach for the synthesis of reversible circuits from the exclusive- OR sum-of-products (ESOP) representation of functions, which makes better use of shared functionality among multiple outputs, resulting in up to 75% minimization of quantum cost compared to the previous approach. This thesis also investigates the previous work on constructing the online testable circuits and points out some design issues. A simple approach for online fault detection is proposed for a particular type of ESOP-based reversible circuit, which is also extended for any type of Toffoli circuits. The proposed online testable designs not only address the problems of the previous designs but also achieve significant improvements of up to 78% and 99% in terms of quantum cost and garbage outputs, respectively.

Recently, researchers have been interested in reversible computing because of its ability to dissipate nearly zero heat and because of its applications in quantum computing and low power VLSI design. Synthesis and testing are two important areas of reversible logic. The thesis first presents an approach for the synthesis of reversible circuits from the exclusive- OR sum-of-products (ESOP) representation of functions, which makes better use of shared functionality among multiple outputs, resulting in up to 75% minimization of quantum cost compared to the previous approach. This thesis also investigates the previous work on constructing the online testable circuits and points out some design issues. A simple approach for online fault detection is proposed for a particular type of ESOP-based reversible circuit, which is also extended for any type of Toffoli circuits. The proposed online testable designs not only address the problems of the previous designs but also achieve significant improvements of up to 78% and 99% in terms of quantum cost and garbage outputs, respectively.

Recently, researchers have been interested in reversible computing because of its ability to dissipate nearly zero heat and because of its applications in quantum computing and low power VLSI design. Synthesis and testing are two important areas of reversible logic. The thesis first presents an approach for the synthesis of reversible circuits from the exclusive- OR sum-of-products (ESOP) representation of functions, which makes better use of shared functionality among multiple outputs, resulting in up to 75% minimization of quantum cost compared to the previous approach. This thesis also investigates the previous work on constructing the online testable circuits and points out some design issues. A simple approach for online fault detection is proposed for a particular type of ESOP-based reversible circuit, which is also extended for any type of Toffoli circuits. The proposed online testable designs not only address the problems of the previous designs but also achieve significant improvements of up to 78% and 99% in terms of quantum cost and garbage outputs, respectively.

As computation spreads from computers to networks of computers, and migrates into cyberspace it ceases to be globally programmable, but it remains programmable indirectly and partially: network computations cannot be controlled, but they can be steered by imposing local constraints on network nodes. The tasks of programming global behaviors through local constraints belong to the area of security. The program particles that assure that a system of local interactions leads towards some desired global goals are called security protocols. They are the software connectors of modern, world wide software systems. As computation spreads beyond cyberspace, into physical and social spaces, new security tasks and problems arise. As computer networks are extended by nodes with physical sensors and controllers, including the humans, and interlaced with social networks, the engineering concepts and techniques of computer security blend with the social processes of security, that evolved since the dawn of mankind. These new connectors for computational and social software require a new discipline of programming of global behaviors through local constraints. Since the new discipline seems to be emerging from a combination of established models of security protocols with older methods of procedural programming, we use the name procedures for these new connectors, that generalize protocols. In the present paper we propose actor-networks as a formal model of computation in heterogenous networks of computers, humans and their devices, where these new procedures run; and we introduce Procedure Derivation Logic (PDL) as a framework for reasoning about security in actor-networks. On the way, we survey the guiding ideas of Protocol Derivation Logic (also PDL) that evolved through our work in security in last 10 years. Both formalisms are geared towards graphic reasoning and, ultimately, tool support. We illustrate their workings by analysing a form of two-factor authentication., Submitted to Formal Aspects of Computing. Prepared in collaboration with Royal Holloway University of London and Universiteit Twente.

Statistical relational learning (SRL) is the area of machine learning that integrates both first-order logic and probabilistic graphical models. The advantage of these formalisms is that they can handle both uncertainty and structured/relational data. As a result, they are widely used in domains like social network analysis, biological data analysis, and natural language processing. Bayesian Logic Programs (BLPs), which integrate both first-order logic and Bayesian networks are a powerful SRL formalism developed in the recent past. In this proposal, we focus on applying BLPs to two real worlds tasks--plan recognition and machine reading. Plan recognition is the task of predicting an agent's top-level plans based on its observed actions. It is an abductive reasoning task that involves inferring cause from effect. In the first part of the proposal, we develop an approach to abductive plan recognition using BLPs. Since BLPs employ logical deduction to construct the networks, they cannot be used effectively for plan recognition as is. Therefore, we extend BLPs to use logical abduction to construct Bayesian networks and call the resulting model Bayesian Abductive Logic Programs (BALPs). Experimental evaluation on three benchmark data sets demonstrate that BALPs outperform the existing state-of-art methods like Markov Logic Networks (MLNs) for plan recognition. For future work, we propose to apply BLPs to the task of machine reading, which involves automatic extraction of knowledge from natural language text. Present day information extraction (IE) systems that are trained for machine reading are limited by their ability to extract only factual information that is stated explicitly in the text. We propose to improve the performance of an off-the-shelf IE system by inducing general knowledge rules about the domain using the facts already extracted by the IE system., Supported in part by NSF grant EIA-0303609.

This dissertation describes progress on programming with domain-specific specification logics in dependently typed programming languages. Domain-specific logics are a promising way to verify software, using a logic tailored to a style of programming or an application domain. First goal of the research is to show that it is possible to define, study, automate, and use domain-specific logics within a dependently typed programming language. We demonstrate this with an example showing how to embed a security-typed language using dependent types. This suggests that better support for programming with logics in type theory will facilitate this style of program verification. The central notion in logic is consequence - entailment from premises to conclusions - and two notions of consequence are necessary for programming with logics: derivability, which captures uniform reasoning, and admissibility, which captures inductive proofs and functional programs. Presently, derivability is better supported in LF-based proof assistants such as Twelf, Delphin, and Beluga, whereas admissibility is better supported in proof assistants based on Martin-Loef type theory. Second contribution is to show that it is possible to implement, within a dependently typed programming language, a logical framework that allows derivability and admissibility to be mixed in novel and interesting ways. The framework is simply-typed, suitable for programming with abstract syntax but not logical derivations. Third contribution is to generalize this framework to dependent types We describe Directed Type Theory (DTT), a dependent type theory, which equips each type with a notion of transformation on its elements. The structural properties of a logic arise as a special case, considering a type of contexts equipped with an appropriate notion of transformation. DTT generalizes recent connections between type theory, homotopy theory, and category theory to the asymmetric case.

In recent years ternary reversible logic has caught the attention of researchers because of its enormous potential in different fields, in particular quantum computing. It is desirable that any future reversible technology should be fault tolerant and have low power consumption; hence developing testing techniques in this area is of great importance. In this work we propose a design for an online testable ternary reversible circuit. The proposed design can implement almost all of the ternary logic operations and is also capable of testing the reversible ternary network in real time (online). The error detection unit is also constructed in a reversible manner, which results in an overall circuit which meets the requirements of reversible computing. We have also proposed an upgrade of the initial design to make the design more optimized. Several ternary benchmark circuits have been implemented using the proposed approaches. The number of gates required to implement the benchmarks for each approach have also been compared. To our knowledge this is the first such circuit in ternary with integrated online testability feature.

In recent years ternary reversible logic has caught the attention of researchers because of its enormous potential in different fields, in particular quantum computing. It is desirable that any future reversible technology should be fault tolerant and have low power consumption; hence developing testing techniques in this area is of great importance. In this work we propose a design for an online testable ternary reversible circuit. The proposed design can implement almost all of the ternary logic operations and is also capable of testing the reversible ternary network in real time (online). The error detection unit is also constructed in a reversible manner, which results in an overall circuit which meets the requirements of reversible computing. We have also proposed an upgrade of the initial design to make the design more optimized. Several ternary benchmark circuits have been implemented using the proposed approaches. The number of gates required to implement the benchmarks for each approach have also been compared. To our knowledge this is the first such circuit in ternary with integrated online testability feature.

In recent years ternary reversible logic has caught the attention of researchers because of its enormous potential in different fields, in particular quantum computing. It is desirable that any future reversible technology should be fault tolerant and have low power consumption; hence developing testing techniques in this area is of great importance. In this work we propose a design for an online testable ternary reversible circuit. The proposed design can implement almost all of the ternary logic operations and is also capable of testing the reversible ternary network in real time (online). The error detection unit is also constructed in a reversible manner, which results in an overall circuit which meets the requirements of reversible computing. We have also proposed an upgrade of the initial design to make the design more optimized. Several ternary benchmark circuits have been implemented using the proposed approaches. The number of gates required to implement the benchmarks for each approach have also been compared. To our knowledge this is the first such circuit in ternary with integrated online testability feature.

In recent years ternary reversible logic has caught the attention of researchers because of its enormous potential in different fields, in particular quantum computing. It is desirable that any future reversible technology should be fault tolerant and have low power consumption; hence developing testing techniques in this area is of great importance. In this work we propose a design for an online testable ternary reversible circuit. The proposed design can implement almost all of the ternary logic operations and is also capable of testing the reversible ternary network in real time (online). The error detection unit is also constructed in a reversible manner, which results in an overall circuit which meets the requirements of reversible computing. We have also proposed an upgrade of the initial design to make the design more optimized. Several ternary benchmark circuits have been implemented using the proposed approaches. The number of gates required to implement the benchmarks for each approach have also been compared. To our knowledge this is the first such circuit in ternary with integrated online testability feature.

In recent years ternary reversible logic has caught the attention of researchers because of its enormous potential in different fields, in particular quantum computing. It is desirable that any future reversible technology should be fault tolerant and have low power consumption; hence developing testing techniques in this area is of great importance. In this work we propose a design for an online testable ternary reversible circuit. The proposed design can implement almost all of the ternary logic operations and is also capable of testing the reversible ternary network in real time (online). The error detection unit is also constructed in a reversible manner, which results in an overall circuit which meets the requirements of reversible computing. We have also proposed an upgrade of the initial design to make the design more optimized. Several ternary benchmark circuits have been implemented using the proposed approaches. The number of gates required to implement the benchmarks for each approach have also been compared. To our knowledge this is the first such circuit in ternary with integrated online testability feature.

This work studies new algorithms and data structures that are useful in the context of program verification. As computers have become more and more ubiquitous in our modern societies, an increasingly large number of computer-based systems are considered safety-critical. Such systems are characterized by the fact that a failure or a bug (computer error in the computing jargon) could potentially cause large damage, whether in loss of life, environmental damage, or economic damage. For safety-critical systems, the industrial software engineering community increasingly calls for using techniques which provide some formal assurance that a certain piece of software is correct.One of the most successful program verification techniques is model checking, in which programs are typically abstracted by a finite-state machine. After this abstraction step, properties (typically in the form of some temporal logic formula) can be checked against the finite-state abstraction, with the help of automated tools. Alternating automata play an important role in this context, since many temporal logics on words and trees can be efficiently translated into those automata. This property allows for the reduction of model checking to automata-theoretic questions and is called the automata-theoretic approach to model checking. In this work, we provide three novel approaches for the analysis (emptiness checking) of alternating automata over finite and infinite words. First, we build on the successful framework of antichains to devise new algorithms for LTL satisfiability and model checking, using alternating automata. These algorithms combine antichains with reduced ordered binary decision diagrams in order to handle the exponentially large alphabets of the automata generated by the LTL translation. Second, we develop new abstraction and refinement algorithms for alternating automata, which combine the use of antichains with abstract interpretation, in order to handle ever larger instances o, Doctorat en Sciences, info:eu-repo/semantics/nonPublished

In recent years ternary reversible logic has caught the attention of researchers because of its enormous potential in different fields, in particular quantum computing. It is desirable that any future reversible technology should be fault tolerant and have low power consumption; hence developing testing techniques in this area is of great importance. In this work we propose a design for an online testable ternary reversible circuit. The proposed design can implement almost all of the ternary logic operations and is also capable of testing the reversible ternary network in real time (online). The error detection unit is also constructed in a reversible manner, which results in an overall circuit which meets the requirements of reversible computing. We have also proposed an upgrade of the initial design to make the design more optimized. Several ternary benchmark circuits have been implemented using the proposed approaches. The number of gates required to implement the benchmarks for each approach have also been compared. To our knowledge this is the first such circuit in ternary with integrated online testability feature.

In recent years ternary reversible logic has caught the attention of researchers because of its enormous potential in different fields, in particular quantum computing. It is desirable that any future reversible technology should be fault tolerant and have low power consumption; hence developing testing techniques in this area is of great importance. In this work we propose a design for an online testable ternary reversible circuit. The proposed design can implement almost all of the ternary logic operations and is also capable of testing the reversible ternary network in real time (online). The error detection unit is also constructed in a reversible manner, which results in an overall circuit which meets the requirements of reversible computing. We have also proposed an upgrade of the initial design to make the design more optimized. Several ternary benchmark circuits have been implemented using the proposed approaches. The number of gates required to implement the benchmarks for each approach have also been compared. To our knowledge this is the first such circuit in ternary with integrated online testability feature.

In recent years ternary reversible logic has caught the attention of researchers because of its enormous potential in different fields, in particular quantum computing. It is desirable that any future reversible technology should be fault tolerant and have low power consumption; hence developing testing techniques in this area is of great importance. In this work we propose a design for an online testable ternary reversible circuit. The proposed design can implement almost all of the ternary logic operations and is also capable of testing the reversible ternary network in real time (online). The error detection unit is also constructed in a reversible manner, which results in an overall circuit which meets the requirements of reversible computing. We have also proposed an upgrade of the initial design to make the design more optimized. Several ternary benchmark circuits have been implemented using the proposed approaches. The number of gates required to implement the benchmarks for each approach have also been compared. To our knowledge this is the first such circuit in ternary with integrated online testability feature.

In recent years ternary reversible logic has caught the attention of researchers because of its enormous potential in different fields, in particular quantum computing. It is desirable that any future reversible technology should be fault tolerant and have low power consumption; hence developing testing techniques in this area is of great importance. In this work we propose a design for an online testable ternary reversible circuit. The proposed design can implement almost all of the ternary logic operations and is also capable of testing the reversible ternary network in real time (online). The error detection unit is also constructed in a reversible manner, which results in an overall circuit which meets the requirements of reversible computing. We have also proposed an upgrade of the initial design to make the design more optimized. Several ternary benchmark circuits have been implemented using the proposed approaches. The number of gates required to implement the benchmarks for each approach have also been compared. To our knowledge this is the first such circuit in ternary with integrated online testability feature.

In recent years ternary reversible logic has caught the attention of researchers because of its enormous potential in different fields, in particular quantum computing. It is desirable that any future reversible technology should be fault tolerant and have low power consumption; hence developing testing techniques in this area is of great importance. In this work we propose a design for an online testable ternary reversible circuit. The proposed design can implement almost all of the ternary logic operations and is also capable of testing the reversible ternary network in real time (online). The error detection unit is also constructed in a reversible manner, which results in an overall circuit which meets the requirements of reversible computing. We have also proposed an upgrade of the initial design to make the design more optimized. Several ternary benchmark circuits have been implemented using the proposed approaches. The number of gates required to implement the benchmarks for each approach have also been compared. To our knowledge this is the first such circuit in ternary with integrated online testability feature.

This work studies new algorithms and data structures that are useful in the context of program verification. As computers have become more and more ubiquitous in our modern societies, an increasingly large number of computer-based systems are considered safety-critical. Such systems are characterized by the fact that a failure or a bug (computer error in the computing jargon) could potentially cause large damage, whether in loss of life, environmental damage, or economic damage. For safety-critical systems, the industrial software engineering community increasingly calls for using techniques which provide some formal assurance that a certain piece of software is correct.One of the most successful program verification techniques is model checking, in which programs are typically abstracted by a finite-state machine. After this abstraction step, properties (typically in the form of some temporal logic formula) can be checked against the finite-state abstraction, with the help of automated tools. Alternating automata play an important role in this context, since many temporal logics on words and trees can be efficiently translated into those automata. This property allows for the reduction of model checking to automata-theoretic questions and is called the automata-theoretic approach to model checking. In this work, we provide three novel approaches for the analysis (emptiness checking) of alternating automata over finite and infinite words. First, we build on the successful framework of antichains to devise new algorithms for LTL satisfiability and model checking, using alternating automata. These algorithms combine antichains with reduced ordered binary decision diagrams in order to handle the exponentially large alphabets of the automata generated by the LTL translation. Second, we develop new abstraction and refinement algorithms for alternating automata, which combine the use of antichains with abstract interpretation, in order to handle ever larger instances o, Doctorat en Sciences, info:eu-repo/semantics/nonPublished

In this report we summarize our contributions over the period 2006-2010. The principal objective of our work is the design, development and analysis of fundamentally new techniques for the problem of solving conjunctions of difference constraints. This problem is well-known to be equivalent to the problem of checking whether a directed graph (network) with positive and negative weights on its edges has a negative cost cycle (NCCD). The NCCD problem finds applications in a number of different design domains such as Program Verification, Real-Time Scheduling and Operations Research. We have looked at several variants of the NCCD problem, including the lightest negative cycle problem, the Horn constraint problem and the Unit Two Variable Per Inequality constraint problem. Each of the specialized constraint classes Our work has resulted in numerous publications in respected journals and conferences., The original document contains color images.

Computing systems designed using reconfigurable hardware are increasingly composed using a number of different Intellectual Property (IP) cores, which are often provided by third-party vendors that may have different levels of trust. Unlike traditional software where hardware resources are mediated using an operating system, IP cores have fine-grain control over the underlying reconfigurable hardware. To address this problem, the embedded systems community requires novel security primitives that address the realities of modern reconfigurable hardware. In this work, we propose security primitives using ideas centered around the notion of "moats and drawbridges." The primitives encompass four design properties: logical isolation, interconnect traceability, secure reconfigurable broadcast, and configuration scrubbing. Each of these is a fundamental operation with easily understood formal properties, yet they map cleanly and efficiently to a wide variety of reconfigurable devices. We carefully quantify the required overheads of the security techniques on modern FPGA architectures across a number of different applications., Published in ACM Transactions on Reconfigurable Technology and Systems, v3, n2, article 10, May 2010.

This paper proposes a design method for floating-point numerical function generators (NFGs) using multi-valued decision diagrams (MDDs). Our method applies to monotone elementary functions in which real values are converted into integer values that are represented by edge-valued MDDs (EVMDDs). We show that EVMDDs use fewer nodes by one or two orders of magnitude than two other types of decision diagrams, MTBDDs and BMDs. EVMDDs produce fast and compact floating-point NFGs for real-valued elementary functions, with a speed improvement of 86% over a recently proposed floating-point implementation., Presented at the International Symposium on Multiple-Valued Logic (39th) held in Naha, Japan on 21-23 May 2009.

This report describes the theoretical underpinnings of the PENG system. Designed by Rolf Schwitter, Marc Tilbrook, et al. at the Centre for Language Technology at Macquarie University, the system incorporates a text editor where authors write text in a controlled language called PENG. Authors of PENG text do not need to remember the restrictions placed on the language, since the PENG text editor guides the writing process. It does this by indicating the possible sentence constructs allowable from the current input. A controlled language processor translates PENG text to a logical theory which can then be checked for consistency and informativity, and may also be used for question-answering by third-party reasoning services. Although PENG is still a prototype, and has a number of issues, the system shows potential as a useful tool., The original document contains color images.

In this project, the PI introduced a specification language named Timed Planning, which is an extension of Timed CSP with the capability of stating more complicated timing behaviors for processes and events. They also developed a reasoning mechanism for Timed Planning based on Constraint Logic Programming. They model the Pearl Harbor Attack plan to demonstrate the capability of their approach for modeling time based military plans with critical timing constraints. Their approach is capable to handle the extended job-shop scheduling problems. In their work, the job shop scheduling problems with extensions can be naturally modeled as Timed Planning processes, whose complete executions correspond to feasible schedules. By using CLP based reasoning mechanism, the optimal scheduler which is an execution with the minimum execution time, can be found.