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.

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.

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.

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.<p>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 of alternating automata. Finally, we define a new symbolic data structure, coined lattice-valued binary decision diagrams that is particularly well-suited for the encoding of transition functions of alternating automata over symbolic alphabets. All of these works are supported with empirical evaluations that confirm the practical usefulness of our approaches. / Ce travail traite de l'étude de nouveaux algorithmes et structures de données dont l'usage est destiné à la vérification de programmes. Les ordinateurs sont de plus en plus présents dans notre vie quotidienne et, de plus en plus souvent, ils se voient confiés des tâches de nature critique pour la sécurité. Ces systèmes sont caractérisés par le fait qu'une panne ou un bug (erreur en jargon informatique) peut avoir des effets potentiellement désastreux, que ce soit en pertes humaines, dégâts environnementaux, ou économiques. Pour ces systèmes critiques, les concepteurs de systèmes industriels prônent de plus en plus l'usage de techniques permettant d'obtenir une assurance formelle de correction.<p><p>Une des techniques de vérification de programmes les plus utilisées est le model checking, avec laquelle les programmes sont typiquement abstraits par une machine a états finis. Après cette phase d'abstraction, des propriétés (typiquement sous la forme d'une formule de logique temporelle) peuvent êtres vérifiées sur l'abstraction à espace d'états fini, à l'aide d'outils de vérification automatisés. Les automates alternants jouent un rôle important dans ce contexte, principalement parce que plusieurs logiques temporelle peuvent êtres traduites efficacement vers ces automates. Cette caractéristique des automates alternants permet de réduire le model checking des logiques temporelles à des questions sur les automates, ce qui est appelé l'approche par automates du model checking. Dans ce travail, nous étudions trois nouvelles approches pour l'analyse (le test du vide) desautomates alternants sur mots finis et infinis. Premièrement, nous appliquons l'approche par antichaînes (utilisée précédemment avec succès pour l'analyse d'automates) pour obtenir de nouveaux algorithmes pour les problèmes de satisfaisabilité et du model checking de la logique temporelle linéaire, via les automates alternants.Ces algorithmes combinent l'approche par antichaînes avec l'usage des ROBDD, dans le but de gérer efficacement la combinatoire induite par la taille exponentielle des alphabets d'automates générés à partir de LTL. Deuxièmement, nous développons de nouveaux algorithmes d'abstraction et raffinement pour les automates alternants, combinant l'usage des antichaînes et de l'interprétation abstraite, dans le but de pouvoir traiter efficacement des automates de grande taille. Enfin, nous définissons une nouvelle structure de données, appelée LVBDD (Lattice-Valued Binary Decision Diagrams), qui permet un encodage efficace des fonctions de transition des automates alternants sur alphabets symboliques. Tous ces travaux ont fait l'objet d'implémentations et ont été validés expérimentalement. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Indiana University-Purdue University Indianapolis (IUPUI) / A Laboratory Information Management Systems (LIMS) is designed to manage laboratory processes and data. It has the ability to extend the core functionality of the LIMS through configuration tools and add-on modules to support the implementation of complex laboratory workflows. The purpose of this project is to demonstrate how laboratory data and processes from a complex workflow can be implemented using a LIMS. Genomic samples have become an important part of the drug development process due to advances in molecular testing technology. This technology evaluates genomic material for disease markers and provides efficient, cost-effective, and accurate results for a growing number of clinical indications. The preparation of the genomic samples for evaluation requires a complex laboratory process called the precision aliquotting workflow. The precision aliquotting workflow processes genomic samples into precisely created aliquots for analysis. The workflow is defined by a set of aliquotting scheme attributes that are executed based on scheme specific rules logic. The aliquotting scheme defines the attributes of each aliquot based on the achieved sample recovery of the genomic sample. The scheme rules logic executes the creation of the aliquots based on the scheme definitions. LabWare LIMS is a Windows® based open architecture system that manages laboratory data and workflow processes. A LabWare LIMS model was developed to implement the precision aliquotting workflow using a combination of core functionality and configured code.