In this thesis we examine the relationship between hypersequent and some types of labelled sequent calculi for a subset of intermediate logics—logics between intuitionistic (Int), and classical logics—that have geometric Kripke semantics, which we call Int∗/Geo. We introduce a novel calculus for a fragment of first-order classical logic, which we call partially-shielded formulae (or PSF for short), that is adequate for expressing the semantic validity of formulae in Int∗/Geo, and apply techniques from correspondence theory to provide translations of hypersequents, simply labelled sequents and relational sequents (simply labelled sequents with relational formulae) into PSF. Using these translations, we show that hypersequents and simply labelled sequents for calculi in Int∗/Geo share the same models. We also use these translations to justify various techniques that we introduce for translating simply labelled sequents into relational sequents and vice versa. In particular, we introduce a technique called "transitive unfolding" for translating relational sequents into simply labelled sequents (and by extension, hypersequents) which preserves linear models in Int∗/Geo. We introduce syntactic translations between hypersequent calculi and simply labelled sequent calculi. We apply these translations to a novel hypersequent framework HG3ipm∗ for some logics in Int∗/Geo to obtain a corresponding simply labelled sequent framework LG3ipm∗, and to an existing simply labelled calculus for Int from the literature to obtain a novel hypersequent calculus for Int. We introduce methods for translating a simply labelled sequent calculus into a cor- responding relational calculus, and apply these methods to LG3ipm∗ to obtain a novel relational framework RG3ipm∗ that bears similarities to existing calculi from the literature. We use transitive unfolding to translate proofs in RG3ipm∗ into proofs in LG3ipm∗ and HG3ipm∗ with the communication rule, which corresponds to the semantic restriction to linear models.

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. / xii, 82 leaves : ill. ; 29 cm

Thesis (Ph.D)--Computing, Georgia Institute of Technology, 2009. / Committee Chair: Palem, Krishna V.; Committee Member: Lim, Sung Kyu; Committee Member: Loh, Gabriel H.; Committee Member: Mudge, Trevor; Committee Member: Yalamanchili, Sudhakar. Part of the SMARTech Electronic Thesis and Dissertation Collection.

Thesis (Ph.D.) - Carleton University, 2007. / Includes bibliographical references (p. 220-226). Also available in electronic format on the Internet.

We investigate the expressive power of different fragments of higher-order logics over finite relational structures (or equivalently, relational databases) with special emphasis in higher-order logics of order greater than or equal three. Our main results concern the study of the effect on the expressive power of higher-order logics, of simultaneously bounding the arity of the higher-order variables and the alternation of quantifiers. Let AAi(r,m) be the class of (i + 1)-th order logic formulae where all quantifiers are grouped together at the beginning of the formulae, forming m alternating blocks of consecutive existential and universal quantifiers, and such that the maximal-arity (a generalization of the concept of arity, not just the maximal of the arities of the quantified variables) of the higher-order variables is bounded by r. Note that, the order of the quantifiers in the prefix may be mixed. We show that, for every i [greater than or equal to] 1, the resulting AAi hierarchy of formulae of (i + 1)-th order logic is proper. This extends a result by Makowsky and Pnueli who proved that the same hierarchy in second-order logic is proper. In both cases the strategy used to prove the results consists in considering the set AUTOSAT(F) of formulae in a given logic F which, represented as finite structures, satisfy themselves. We then use a similar strategy to prove that the classes of [Sigma superscript i subscript m union Pi superscript i subscript m] formulae in which the higher-order variables of all orders up to i+1 have maximal-arity at most r, also induce a proper hierarchy in each higher-order logic of order i [greater than or equal to] 3. It is not known whether the correspondent hierarchy in second-order logic is proper. Using the concept of finite model truth definitions introduced by M. Mostowski, we give a sufficient condition for that to be the case. We also study the complexity of the set AUTOSAT(F) and show that when F is one of the prenex fragments [Sigma superscript 1 subscript m] of second-order logic, it follows that AUTOSAT(F) becomes a complete problem for the corresponding prenex fragment [Sigma superscript 2 subscript m] of third-order logic. Finally, aiming to provide the background for a future line of research in higher-order logics, we take a closer look to the restricted second-order logic SO[superscript w] introduced by Dawar. We further investigate its connection with the concept of relational complexity studied by Abiteboul, Vardi and Vianu. Dawar showed that the existential fragment of SO[superscript w] is equivalent to the nondeterministic inflationary fixed-point logic NFP. Since NFP captures relational NP, it follows that the existential fragment of SO[superscript w] captures relational NP. We give a direct proof, in the style of the proof of Fagin’s theorem, of this fact. We then define formally the concept of relational machine with relational oracle and prove the exact correspondence between the prenex fragments of SO[superscript w] and the levels of the relational polynomial-time hierarchy. This allows us to stablish a direct connection between the relational polynomial hierarchy and SO without using the Abiteboul and Vianu normal form for relational machines.

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. / xii, 92 leaves : ill. ; 29 cm

Parameter variations, noise susceptibility, and increasing energy dissipation of CMOS devices have been recognized as major challenges in circuit and micro-architecture design in the nanometer regime. Among these, parameter variations and noise susceptibility are increasingly causing CMOS devices to behave in an "unreliable" or "probabilistic" manner. To address these challenges, a shift in design paradigm, from current day deterministic designs to "statistical" or "probabilistic" designs is deemed inevitable. Motivated by these considerations, I introduce and define probabilistic Boolean logic, whose logical operators are by definition "correct" with a probability 1/2 <= p <= 1. While most of the laws of conventional Boolean logic can be naturally extended to be valid in the probabilistic case, there are a few significant departures. We also show that computations realized using implicitly probabilistic Boolean operators are more energy efficient than their counterparts which use explicit sources of randomness, in the context of probabilistic Boolean circuits as well as probabilistic models with state, Rabin automata. To demonstrate the utility of implicitly probabilistic elements, we study a family of probabilistic architectures: the probabilistic system-on-a-chip PSOC, based on CMOS devices rendered probabilistic due to noise, referred to as probabilistic CMOS or PCMOS devices. These architectures yield significant improvements, both in the energy consumed as well as in the performance in the context of probabilistic or randomized applications with broad utility. Finally, we extend the consideration of probability of correctness to arithmetic operations, through probabilistic arithmetic. We show that in the probabilistic context, substantial savings in energy over correct arithmetic operations may be achieved. This is the theoretical basis of the energy savings reported in the video decoding and radar processing applications that has been demonstrated in prior work.

We investigate the expressive power of different fragments of higher-order logics over finite relational structures (or equivalently, relational databases) with special emphasis in higher-order logics of order greater than or equal three. Our main results concern the study of the effect on the expressive power of higher-order logics, of simultaneously bounding the arity of the higher-order variables and the alternation of quantifiers. Let AAi(r,m) be the class of (i + 1)-th order logic formulae where all quantifiers are grouped together at the beginning of the formulae, forming m alternating blocks of consecutive existential and universal quantifiers, and such that the maximal-arity (a generalization of the concept of arity, not just the maximal of the arities of the quantified variables) of the higher-order variables is bounded by r. Note that, the order of the quantifiers in the prefix may be mixed. We show that, for every i [greater than or equal to] 1, the resulting AAi hierarchy of formulae of (i + 1)-th order logic is proper. This extends a result by Makowsky and Pnueli who proved that the same hierarchy in second-order logic is proper. In both cases the strategy used to prove the results consists in considering the set AUTOSAT(F) of formulae in a given logic F which, represented as finite structures, satisfy themselves. We then use a similar strategy to prove that the classes of [Sigma superscript i subscript m union Pi superscript i subscript m] formulae in which the higher-order variables of all orders up to i+1 have maximal-arity at most r, also induce a proper hierarchy in each higher-order logic of order i [greater than or equal to] 3. It is not known whether the correspondent hierarchy in second-order logic is proper. Using the concept of finite model truth definitions introduced by M. Mostowski, we give a sufficient condition for that to be the case. We also study the complexity of the set AUTOSAT(F) and show that when F is one of the prenex fragments [Sigma superscript 1 subscript m] of second-order logic, it follows that AUTOSAT(F) becomes a complete problem for the corresponding prenex fragment [Sigma superscript 2 subscript m] of third-order logic. Finally, aiming to provide the background for a future line of research in higher-order logics, we take a closer look to the restricted second-order logic SO[superscript w] introduced by Dawar. We further investigate its connection with the concept of relational complexity studied by Abiteboul, Vardi and Vianu. Dawar showed that the existential fragment of SO[superscript w] is equivalent to the nondeterministic inflationary fixed-point logic NFP. Since NFP captures relational NP, it follows that the existential fragment of SO[superscript w] captures relational NP. We give a direct proof, in the style of the proof of Fagin’s theorem, of this fact. We then define formally the concept of relational machine with relational oracle and prove the exact correspondence between the prenex fragments of SO[superscript w] and the levels of the relational polynomial-time hierarchy. This allows us to stablish a direct connection between the relational polynomial hierarchy and SO without using the Abiteboul and Vianu normal form for relational machines.

We investigate the expressive power of different fragments of higher-order logics over finite relational structures (or equivalently, relational databases) with special emphasis in higher-order logics of order greater than or equal three. Our main results concern the study of the effect on the expressive power of higher-order logics, of simultaneously bounding the arity of the higher-order variables and the alternation of quantifiers. Let AAi(r,m) be the class of (i + 1)-th order logic formulae where all quantifiers are grouped together at the beginning of the formulae, forming m alternating blocks of consecutive existential and universal quantifiers, and such that the maximal-arity (a generalization of the concept of arity, not just the maximal of the arities of the quantified variables) of the higher-order variables is bounded by r. Note that, the order of the quantifiers in the prefix may be mixed. We show that, for every i [greater than or equal to] 1, the resulting AAi hierarchy of formulae of (i + 1)-th order logic is proper. This extends a result by Makowsky and Pnueli who proved that the same hierarchy in second-order logic is proper. In both cases the strategy used to prove the results consists in considering the set AUTOSAT(F) of formulae in a given logic F which, represented as finite structures, satisfy themselves. We then use a similar strategy to prove that the classes of [Sigma superscript i subscript m union Pi superscript i subscript m] formulae in which the higher-order variables of all orders up to i+1 have maximal-arity at most r, also induce a proper hierarchy in each higher-order logic of order i [greater than or equal to] 3. It is not known whether the correspondent hierarchy in second-order logic is proper. Using the concept of finite model truth definitions introduced by M. Mostowski, we give a sufficient condition for that to be the case. We also study the complexity of the set AUTOSAT(F) and show that when F is one of the prenex fragments [Sigma superscript 1 subscript m] of second-order logic, it follows that AUTOSAT(F) becomes a complete problem for the corresponding prenex fragment [Sigma superscript 2 subscript m] of third-order logic. Finally, aiming to provide the background for a future line of research in higher-order logics, we take a closer look to the restricted second-order logic SO[superscript w] introduced by Dawar. We further investigate its connection with the concept of relational complexity studied by Abiteboul, Vardi and Vianu. Dawar showed that the existential fragment of SO[superscript w] is equivalent to the nondeterministic inflationary fixed-point logic NFP. Since NFP captures relational NP, it follows that the existential fragment of SO[superscript w] captures relational NP. We give a direct proof, in the style of the proof of Fagin’s theorem, of this fact. We then define formally the concept of relational machine with relational oracle and prove the exact correspondence between the prenex fragments of SO[superscript w] and the levels of the relational polynomial-time hierarchy. This allows us to stablish a direct connection between the relational polynomial hierarchy and SO without using the Abiteboul and Vianu normal form for relational machines.

We investigate the expressive power of different fragments of higher-order logics over finite relational structures (or equivalently, relational databases) with special emphasis in higher-order logics of order greater than or equal three. Our main results concern the study of the effect on the expressive power of higher-order logics, of simultaneously bounding the arity of the higher-order variables and the alternation of quantifiers. Let AAi(r,m) be the class of (i + 1)-th order logic formulae where all quantifiers are grouped together at the beginning of the formulae, forming m alternating blocks of consecutive existential and universal quantifiers, and such that the maximal-arity (a generalization of the concept of arity, not just the maximal of the arities of the quantified variables) of the higher-order variables is bounded by r. Note that, the order of the quantifiers in the prefix may be mixed. We show that, for every i [greater than or equal to] 1, the resulting AAi hierarchy of formulae of (i + 1)-th order logic is proper. This extends a result by Makowsky and Pnueli who proved that the same hierarchy in second-order logic is proper. In both cases the strategy used to prove the results consists in considering the set AUTOSAT(F) of formulae in a given logic F which, represented as finite structures, satisfy themselves. We then use a similar strategy to prove that the classes of [Sigma superscript i subscript m union Pi superscript i subscript m] formulae in which the higher-order variables of all orders up to i+1 have maximal-arity at most r, also induce a proper hierarchy in each higher-order logic of order i [greater than or equal to] 3. It is not known whether the correspondent hierarchy in second-order logic is proper. Using the concept of finite model truth definitions introduced by M. Mostowski, we give a sufficient condition for that to be the case. We also study the complexity of the set AUTOSAT(F) and show that when F is one of the prenex fragments [Sigma superscript 1 subscript m] of second-order logic, it follows that AUTOSAT(F) becomes a complete problem for the corresponding prenex fragment [Sigma superscript 2 subscript m] of third-order logic. Finally, aiming to provide the background for a future line of research in higher-order logics, we take a closer look to the restricted second-order logic SO[superscript w] introduced by Dawar. We further investigate its connection with the concept of relational complexity studied by Abiteboul, Vardi and Vianu. Dawar showed that the existential fragment of SO[superscript w] is equivalent to the nondeterministic inflationary fixed-point logic NFP. Since NFP captures relational NP, it follows that the existential fragment of SO[superscript w] captures relational NP. We give a direct proof, in the style of the proof of Fagin’s theorem, of this fact. We then define formally the concept of relational machine with relational oracle and prove the exact correspondence between the prenex fragments of SO[superscript w] and the levels of the relational polynomial-time hierarchy. This allows us to stablish a direct connection between the relational polynomial hierarchy and SO without using the Abiteboul and Vianu normal form for relational machines.