Dissertations / Theses on the topic 'Higher order logics'
To see the other types of publications on this topic, follow the link: Higher order logics.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Higher order logics.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Assaf, Ali. "A framework for defining computational higher-order logics." Palaiseau, Ecole polytechnique, 2015. https://theses.hal.science/tel-01235303v4/document.
Full textAbstract:
The main aim of this thesis is to make formal proofs more universal by expressing them in a common logical framework. More specifically, we use the lambda-Pi-calculus modulo rewriting, a lambda calculus equipped with dependent types and term rewriting, as a language for defining logics and expressing proofs in those logics. By representing propositions as types and proofs as programs in this language, we design translations of various systems in a way that is efficient and that preserves their meaning. These translations can then be used for independent proof checking and proof interoperability. In this work, we focus on the translation of logics based on type theory that allow both computation and higher-order quantification as steps of reasoning. Pure type systems are a well-known example of such computational higher-order systems, and form the basis of many modern proof assistants. We design a translation of functional pure type systems to the lambda-Pi-calculus modulo rewriting based on previous work by Cousineau and Dowek. The translation preserves typing, and in particular it therefore also preserves computation. We show that the translation is adequate by proving that it is conservative with respect to the original systems. We also adapt the translation to support universe cumulativity, a feature that is present in modern systems such as intuitionistic type theory and the calculus of inductive constructions. We propose to use explicit coercions to handle the implicit subtyping that is present in cumulativity, bridging the gap between pure type systems and type theory with universes à la Tarski. We also show how to preserve the expressivity of the original systems by adding equations to guarantee that types have a unique term representation, thus maintaining the completeness of the translation. The results of this thesis have been applied in automated proof translation tools. We implemented programs that automatically translate the proofs of HOL, Coq, and Matita, to Dedukti, a type-checker for the lambda-Pi-calculus modulo rewriting. These proofs can then be re-checked and combined together to form new theories in Dedukti, which thus serves as an independent proof checker and a platform for proof interoperability. We tested our tools on a variety of libraries. Experimental results confirm that our translations are correct and that they are efficient compared to the state of the art.
2
Freire, Cibele Matos. "Complexidade descritiva das lÃgicas de ordem superior com menor ponto fixo e anÃlise de expressividade de algumas lÃgicas modais." Universidade Federal do CearÃ, 2010. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=6359.
Full textAbstract:
Em Complexidade Descritiva investigamos o uso de logicas para caracterizar classes
problemas pelo vies da complexidade. Desde 1974, quando Fagin provou que NP e capturado
pela logica existencial de segunda-ordem, considerado o primeiro resultado da area,
outras relac~oes entre logicas e classes de complexidade foram estabelecidas. Os resultados
mais conhecidos normalmemte envolvem logica de primeira-ordem e suas extens~oes,
e classes de complexidade polinomiais em tempo ou espaco. Alguns exemplos sÃo que a
logica de primeira-ordem estendida com o operador de menor ponto xo captura a clsse
P e que a logica de segunda-ordem estendida com o operador de fecho transitivo captura
a classe PSPACE. Nesta dissertaÃÃo, analisaremos inicialmente a expressividade de algumas
logicas modais com relacÃo ao problema de decisÃo REACH e veremos que e possvel
expressa-lo com as logicas temporais CTL e CTL. Analisaremos tambem o uso combinado
de logicas de ordem superior com o operador de menor ponto xo e obteremos como
resultado que cada nvel dessa hierarquia captura cada nvel da hierarquia determinstica
em tempo exponencial. Como corolario, provamos que a hierarquia de HOi(LFP) nÃo
colapsa, ou seja, HOi(LFP) HOi+1(LFP)In Descriptive Complexity, we investigate the use of logics to characterize computational classes os problems through complexity. Since 1974, when Fagin proved that the class NP is captured by existential second-order logic, considered the rst result in this area, other relations between logics and complexity classes have been established. Wellknown results usually involve rst-order logic and its extensions, and complexity classes in polynomial time or space. Some examples are that the rst-order logic extended by the least xed-point operator captures the class P and the second-order logic extended by the transitive closure operator captures the class PSPACE. In this dissertation, we will initially analyze the expressive power of some modal logics with respect to the decision problem REACH and see that is possible to express it with temporal logics CTL and CTL. We will also analyze the combined use of higher-order logics extended by the least xed-point operator and obtain as result that each level of this hierarchy captures each level of the deterministic exponential time hierarchy. As a corollary, we will prove that the hierarchy of HOi(LFP), for i 2, does not collapse, that is, HOi(LFP) HOi+1(LFP)
3
TEICA, ELENA. "FORMAL CORRECTNESS AND COMPLETENESS FOR A SET OF UNINTERPRETED RTL TRANSFORMATIONS." University of Cincinnati / OhioLINK, 2001. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1001432470.
Full text
4
Freire, Cibele Matos. "Complexidade descritiva das lógicas de ordem superior com menor ponto fixo e análise de expressividade de algumas lógicas modais." reponame:Repositório Institucional da UFC, 2010. http://www.repositorio.ufc.br/handle/riufc/17668.
Full textAbstract:
Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-14T19:46:59Z
No. of bitstreams: 1
2010_dis_cmfreire.pdf: 426798 bytes, checksum: 4ad13c09839833ee22b0396a445e8a26 (MD5)Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-14T19:48:16Z (GMT) No. of bitstreams: 1 2010_dis_cmfreire.pdf: 426798 bytes, checksum: 4ad13c09839833ee22b0396a445e8a26 (MD5)
Made available in DSpace on 2016-06-14T19:48:16Z (GMT). No. of bitstreams: 1 2010_dis_cmfreire.pdf: 426798 bytes, checksum: 4ad13c09839833ee22b0396a445e8a26 (MD5) Previous issue date: 2010
In Descriptive Complexity, we investigate the use of logics to characterize computational classes os problems through complexity. Since 1974, when Fagin proved that the class NP is captured by existential second-order logic, considered the rst result in this area, other relations between logics and complexity classes have been established. Wellknown results usually involve rst-order logic and its extensions, and complexity classes in polynomial time or space. Some examples are that the rst-order logic extended by the least xed-point operator captures the class P and the second-order logic extended by the transitive closure operator captures the class PSPACE. In this dissertation, we will initially analyze the expressive power of some modal logics with respect to the decision problem REACH and see that is possible to express it with temporal logics CTL and CTL . We will also analyze the combined use of higher-order logics extended by the least xed-point operator and obtain as result that each level of this hierarchy captures each level of the deterministic exponential time hierarchy. As a corollary, we will prove that the hierarchy of HOi(LFP), for i 2, does not collapse, that is, HOi(LFP) HOi+1(LFP)
Em Complexidade Descritiva investigamos o uso de logicas para caracterizar classes problemas pelo vies da complexidade. Desde 1974, quando Fagin provou que NP e capturado pela logica existencial de segunda-ordem, considerado o primeiro resultado da area, outras relac~oes entre logicas e classes de complexidade foram estabelecidas. Os resultados mais conhecidos normalmemte envolvem logica de primeira-ordem e suas extens~oes, e classes de complexidade polinomiais em tempo ou espaco. Alguns exemplos são que a l ogica de primeira-ordem estendida com o operador de menor ponto xo captura a clsse P e que a l ogica de segunda-ordem estendida com o operador de fecho transitivo captura a classe PSPACE. Nesta dissertação, analisaremos inicialmente a expressividade de algumas l ogicas modais com rela cão ao problema de decisão REACH e veremos que e poss vel express a-lo com as l ogicas temporais CTL e CTL . Analisaremos tamb em o uso combinado de l ogicas de ordem superior com o operador de menor ponto xo e obteremos como resultado que cada n vel dessa hierarquia captura cada n vel da hierarquia determin stica em tempo exponencial. Como corol ario, provamos que a hierarquia de HOi(LFP) não colapsa, ou seja, HOi(LFP) HOi+1(LFP)
FREIRE, Cibele Matos. Complexidade descritiva das lógicas de ordem superior com menor ponto fixo e análise de expressividade de algumas lógicas modais. 2010. 54 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2010.
5
Krishnaswami, Neelakantan R. "Verifying Higher-Order Imperative Programs with Higher-Order Separation Logic." Research Showcase @ CMU, 2012. http://repository.cmu.edu/dissertations/164.
Full textAbstract:
In this thesis I show is that it is possible to give modular correctness proofs of interesting higher-order imperative programs using higher-order separation logic.
To do this, I develop a model higher-order imperative programming language, and develop a program logic for it. I demonstrate the power of my program logic by verifying a series of examples. This includes both realistic patterns of higher-order imperative programming such as the subject-observer pattern, as well as examples demonstrating the use of higher-order logic to reason modularly about highly aliased data structures such as the union-find disjoint set algorithm.
6
Zardini, Elia. "Living on the slippery slope : the nature, sources and logic of vagueness." Thesis, St Andrews, 2008. http://hdl.handle.net/10023/508.
Full text
7
Nesi, Monica. "Formalising process calculi in higher order logic." Thesis, University of Cambridge, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.627495.
Full text
8
Camilleri, Albert John. "Executing behavioural definitions in Higher Order Logic." Thesis, University of Cambridge, 1988. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.232795.
Full textAbstract:
Over the past few years, computer scientists have been using formal verification techniques to show the correctness of digital systems. The verification process, however, is complicated and expensive. Even proofs of simple circuits can involve thousands of logical steps. Often it can be extremely difficult to find correct device specifications and it is desirable that one sets off to prove a correct specification from the start, rather than repeatedly backtrack from the verification process to modify the original definitions after discovering they were incorrect or inaccurate. The main idea presented in the thesis is to amalgamate the techniques of simulation and verification, rather than have the latter replace the former. The result is that behavioural definitions can be simulated until one is reasonably sure that the specification is correct. Furthermore, providing the correctness with respect to these simulated specifications avoids the inadequacies of simulation, where it may not be computationally feasible to demonstrate correctness by exhaustive testing. Simulation here has a different purpose: to get specifications correct as early as possible in the verification process. Its purpose is not to demonstrate the correctness of the implementation - this is done in the verification stage when the very same specifications that were simulated are proven correct. The thesis discusses the implementation of an executable subset of the HOL logic, the version of Higher Order Logic embedded in the HOL theorem prover. It is shown that hardware can be effectively described using both relations and functions; relations being suitable for abstract specification, and functions being suitable for execution. The differences between relational and functional specifications are discussed and illustrated by the verification of an n-bit adder. Techniques for executing functional specifications are presented and various optimisation stratagies are shown which make the execution of the logic efficient. It is further shown that the process of generating optimised functional definitions from relational definitions can be automated. Example simulations of three hardware devices (a factorial machine, a small computer and a communications chip) are presented.
9
Sultana, Nikolai. "Higher-order proof translation." Thesis, University of Cambridge, 2015. https://www.repository.cam.ac.uk/handle/1810/247345.
Full textAbstract:
The case for interfacing logic tools together has been made countless times in the literature, but it is still an important research question. There are various logics and respective tools for carrying out formal developments, but practitioners still lament the difficulty of reliably exchanging mathematical data between tools. Writing proof-translation tools is hard. The problem has both a theoretical side (to ensure that the translation is adequate) and a practical side (to ensure that the translation is feasible and usable). Moreover, the source and target proof formats might be less documented than desired (or even necessary), and this adds a dash of reverse-engineering to what should be a system integration task. This dissertation studies proof translation for higher-order logic. We will look at the qualitative benefits of locating the translation close to the source (where the proof is generated), the target (where the proof is consumed), and in between (as an independent tool from the proof producer and consumer). Two ideas are proposed to alleviate the difficulty of building proof translation tools. The first is a proof translation framework that is structured as a compiler. Its target is specified as an abstract machine, which captures the essential features of its implementations. This framework is designed to be performant and extensible. Second, we study proof transformations that convert refutation proofs from a broad class of consistency-preserving calculi (such as those used by many proof-finding tools) into proofs in validity-preserving calculi (the kind used by many proof-checking tools). The basic method is very simple, and involves applying a single transformation uniformly to all of the source calculi's inferences, rather than applying ad hoc (rule specific) inference interpretations.
10
Fritz, Peter. "Intensional type theory for higher-order contingentism." Thesis, University of Oxford, 2015. http://ora.ox.ac.uk/objects/uuid:b9415266-ad21-494a-9a78-17d2395eb8dd.
Full textAbstract:
Things could have been different, but could it also have been different what things there are? It is natural to think so, since I could have failed to be born, and it is natural to think that I would then not have been anything. But what about entities like propositions, properties and relations? Had I not been anything, would there have been the property of being me? In this thesis, I formally develop and assess views according to which it is both contingent what individuals there are and contingent what propositions, properties and relations there are. I end up rejecting these views, and conclude that even if it is contingent what individuals there are, it is necessary what propositions, properties and relations there are. Call the view that it is contingent what individuals there are first-order contingentism, and the view that it is contingent what propositions, properties and relations there are higher-order contingentism. I bring together the three major contributions to the literature on higher-order contingentism, which have been developed largely independently of each other, by Kit Fine, Robert Stalnaker, and Timothy Williamson. I show that a version of Stalnaker's approach to higher-order contingentism was already explored in much more technical detail by Fine, and that it stands up well to the major challenges against higher-order contingentism posed by Williamson. I further show that once a mistake in Stalnaker's development is corrected, each of his models of contingently existing propositions corresponds to the propositional fragment of one of Fine's more general models of contingently existing propositions, properties and relations, and vice versa. I also show that Stalnaker's theory of contingently existing propositions is in tension with his own theory of counterfactuals, but not with one of the main competing theories, proposed by David Lewis. Finally, I connect higher-order contingentism to expressive power arguments against first-order contingentism. I argue that there are intelligible distinctions we draw with talk about "possible things", such as the claim that there are uncountably many possible stars. Since first-order contingentists hold that there are no possible stars apart from the actual stars, they face the challenge of paraphrasing such talk. I show that even in an infinitary higher-order modal logic, the claim that there are uncountably many possible stars can only be paraphrased if higher-order contingentism is false. I therefore conclude that even if first-order contingentism is true, higher-order contingentism is false.
11
Haftmann, Florian. "Code generation from specifications in higher-order logic." kostenfrei, 2009. https://mediatum2.ub.tum.de/node?id=886023.
Full text
12
Cardell-Oliver, Rachel Mary. "The formal verification of hard real-time systems." Thesis, University of Cambridge, 1992. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.239756.
Full text
13
Berghofer, Stefan. "Proofs, programs and executable specifications in higher order logic." [S.l. : s.n.], 2003. http://deposit.ddb.de/cgi-bin/dokserv?idn=969627661.
Full text
14
Bruse, Florian [Verfasser]. "Extremal fixpoints for higher-order modal logic / Florian Bruse." Kassel : Universitätsbibliothek Kassel, 2020. http://d-nb.info/1220854093/34.
Full text
15
Grellois, Charles. "Semantics of linear logic and higher-order model-checking." Sorbonne Paris Cité, 2016. http://www.theses.fr/2016USPCC024.
Full textAbstract:
Dans cette thèse, nous envisageons des problèmes de model-checking d'ordre supérieur à l'aide d'approches issues de la sémantique et de la logique. Le model-checking d'ordre supérieur étudie la vérification de propriétés, exprimées en logique monadique du second ordre, sur des arbres infinis générés par une classe de systèmes de réécriture appelés schémas de récursion d'ordre supérieur. Ces systèmes sont équivalents au lambda-calcul simplement typé avec récursion, et peuvent donc être étudiés à l'aide d'outils sémantiques. Plus précisément, l'objet de cette thèse est de relier le model-checking d'ordre supérieur à une série de concepts de premier plan en sémantique contemporaine, tels que la logique linéaire et sa sémantique relationnelle, la logique linéaire indexée, les lois distributives entre comonades, les comonades paramétrées et la logique tensorielle. Nous verrons que ces concepts contribuent de façon particulièrement naturelle à l'étude du model-checking d'ordre supérieur. Notre approche débute par une étude du système de types intersection de Kobayashi et Ong, qui permet de typer un schéma de récursion d'ordre supérieur avec les états d'un automate donné encodant une formule de la logique monadique du second ordre. Le schéma admet pour type l'état initial de l'automate si et seulement si l'arbre infini qu'il représente satisfait la propriété encodée par l'automate. En dépit de cette adéquation, le système de types de Kobayashi et Ong a été pensé indépendamment de la connexion existant entre les types intersections et les modèles de la logique linéaire, relation observée par Bucciarelli, Ehrhard, de Carvalho et Terui. Nous avons donc cherché à relier ces deux domaines. Notre analyse nous a permis de définir un système de types intersection dérivé de celui de Kobayashi et Ong, capturant lui aussi le model-checking d'ordre supérieur de façon adéquate. Contrairement au système original, notre système est formulé de façon modale, et correspond à une sémantique finitaire de la logique linéaire obtenue en composant la modalité exponentielle usuelle avec une comonade colorant les formules. Nous équipons cette sémantique de la logique linéaire avec un opérateur de point fixe inductif-coinductif, et obtenons ainsi un modèle du lambda-calcul avec récursion dans lequel l'interprétation d'un schéma de récursion d'ordre supérieur est l'ensemble des états depuis lesquels l'arbre infini qu'il représente est accepté. La finitude de la sémantique nous permet de donner de nouvelles preuves de plusieurs résultats de décidabilité pour des problèmes de model-checking d'ordre supérieur, dont le problème de la sélection formulé récemment par Carayol et Serre. La sémantique finitaire que nous définissons est inspirée du théorème d'écrasement extensionnel d'Ehrhard, qui montre que l'écrasement extensionnel du modèle relationnel de la logique linéaire correspond à sa sémantique finitaire donnée par le modèle de Scott. Ce résultat nous permet de définir dans un premier temps la comonade de coloration et l'opérateur de point fixe inductif-coinductif dans une sémantique quantitative correspondant à une variante infinie (et non-continue) du modèle relationnel de la logique linéaireThis thesis studies problems of higher-order model-checking from a semantic and logical perspective. Higher-order model-checking is concerned with the verification of properties expressed in monadic second-order logic, specified over infinite trees generated by a class of rewriting systems called higher-order recursion schemes. These systems are equivalent to lambda-terms with recursion, and can therefore be studied using semantic methods. The more specific purpose of this thesis is to connect higher-order model-checking to a series of advanced ideas in contemporary semantics, such as linear logic and its relational semantics, indexed linear logic, distributive laws between comonads, parametric comonads and tensorial logic. As we will see, all these ingredients meet and combine surprisingly well with higher-order model-checking. The starting point of our approach is the study of the intersection type system of Kobayashi and Ong. This intersection type system enables one to type a higher-order recursion scheme with states of a given automaton, associated with a formula of monadic second-order logic. The recursion scheme is typable with the initial state of the automaton if and only if the infinite tree it represents satisfies the formula of interest. In spite of this soundness-and-completeness result, the original type system by Kobayashi and Ong was not designed with the connection between intersection types and models of linear logic observed by Bucciarelli, Ehrhard, de Carvalho and Terui in mind. Our work has thus been to connect these two fields. Our analysis leads us to the definition of an alternative intersection type system, which enjoys a similar soundness-and-completeness theorem with respect to higher-order model-checking. In contrast to the original type system by Kobayashi and Ong, our modal formulation is the proof-theoretic counterpart of a finitary semantics of linear logic, obtained by composing the traditional exponential modality with a coloring comonad. We equip the semantics of linear logic with an inductive-coinductive fixpoint operator. We obtain in this way a model of the lambda-calculus with recursion in which the interpretation of a higher-order recursion scheme is the set of states from which the infinite tree it represents is accepted. The finiteness of the semantics enables us to reestablish several results of decidability for higher-order model-checking problems, among which the selection problem recently formulated and proved by Carayol and Serre. This finitary semantics are inspired from the extensional collapse theorem of Ehrhard, who shows that the relational semantics of linear logic collapses extensionally to the finitary semantics provided by Scott lanices. For that reason, we start in a preliminary approach to define the coloring comonad and the inductive-coinductive fixpoint operator in the quantitative semantics provided by an infinitary (and non-continuous) version of the relational model of linear logic
16
Dhingra, Inderpreet Singh. "Formalising an integrated circuit design style in higher order logic." Thesis, University of Cambridge, 1988. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.278296.
Full text
17
Melham, Thomas Frederick. "Formalizing abstraction mechanisms for hardware verification in higher order logic." Thesis, University of Cambridge, 1989. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.334206.
Full text
18
Gilbert, Frédéric. "Extending higher-order logic with predicate subtyping : application to PVS." Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCC009/document.
Full textAbstract:
Le système de types de la logique d'ordre supérieur permet d'exclure certaines expressions indésirables telles que l'application d'un prédicat à lui-même. Cependant, il ne suffit pas pour vérifier des critères plus complexes comme l'absence de divisions par zéro. Cette thèse est consacrée à l’étude d’une extension de la logique d’ordre supérieur appelée sous-typage par prédicats (predicate subtyping), dont l'objet est de rendre l'attribution de types aussi expressive que l'attribution de prédicats. A partir d'un type A et d'un prédicat P(x) de domaine A, le sous-typage par prédicats permet de construire un sous-type de A, noté {x : A | P(x)}, dont les éléments sont les termes t de type A tels que P(t) est démontrable. Le sous-typage par prédicats est au coeur du système PVS.Ce travail présente la formalisation d'un système minimal incluant le sous-typage par prédicats, appelé PVS-Core, ainsi qu'un système de certificats vérifiables pour PVS-Core. Ce deuxième système, appelé PVS-Cert, repose sur l'introduction de termes de preuves et de coercions explicites. PVS-Core et PVS-Cert sont munis d'une notion de conversion correspondant respectivement à l'égalité modulo beta et à l'égalité modulo beta et effacement des coercions, choisi pour établir une correspondance simple entre les deux systèmes.La construction de PVS-Cert est semblable à celle des PTS (Pure Type Systems) avec paires dépendantes et PVS-Cert peut être muni de la notion de beta-sigma-réduction utilisée au coeur de ces systèmes. L'un des principaux théorèmes démontré dans ce travail est la normalisation forte de la réduction sous-jacente à la conversion et de la beta-sigma-réduction. Ce théorème permet d'une part de construire un algorithme de vérification du typage (et des preuves) pour PVS-Cert et d'autre part de démontrer un résultat d'élimination des coupures, utilisé à son tour pour prouver plusieurs propriétés importantes des deux systèmes étudiés. Par ailleurs, il est également démontré que PVS-Cert est une extension conservative du PTS lambda-HOL, et qu'en conséquence PVS-Core est une extension conservative de la logique d'ordre supérieur.Une deuxième partie présente le prototype d'une instrumentation de PVS pour produire des certificats de preuve. Une troisième et dernière partie est consacrée à l'étude de liens entre logique classique et constructive avec la définition d'une traduction par double négation minimale ainsi que la présentation d'un algorithme de constructivisation automatique des preuvesThe type system of higher-order logic allows to exclude some unexpected expressions such as the application of a predicate to itself. However, it is not sufficient to verify more complex criteria such as the absence of divisions by zero. This thesis is dedicated to the study of an extension of higher-order logic, named predicate subtyping, whose purpose is to make the assignment of types as expressive as the assignment of predicates. Starting from a type A and a predicate P(x) of domain A, predicate subtyping allows to build a subtype of A, denoted {x : A | P(x)}, whose elements are the terms t of type A such that P(t) is provable. Predicate subtyping is at the heart of the proof system PVS.This work presents the formalization of a minimal system expressing predicate subtyping, named PVS-Core, as well as a system of verifiable certificates for PVS-Core. This second system, named PVS-Cert, is based on the introduction of proof terms and explicit coercions. PVS-Core and PVS-Cert are equipped with a notion of conversion corresponding respectively to equality modulo beta and to equality modulo beta and the erasure of coercions, chosen to establish a simple correspondence between the two systems.The construction of PVS-Cert is similar to that of PTSs (Pure Type Systems) with dependent pairs and PVS-Cert can be equipped with the notion of beta-sigma-reduction used at the core of these systems. One of the main theorems proved in this work is the strong normalization of both the reduction underlying the conversion and beta-sigma-reduction. This theorem allows, on the one hand, to build a type-checking (and proof-checking) algorithm for PVS-Cert and, on the other hand, to prove a cut elimination result, used in turn to prove important properties of the two studied systems. Furthermore, it is also proved that PVS-Cert is a conservative extension of the PTS lambda-HOL and that, as a consequence, PVS-Core is a conservative extension of higher-order logic.A second part presents the prototype of an instrumentation of PVS to generate proof certificates. A third and final part is dedicated to the study of links between classical and constructive logic, with the definition of a minimal double-negation translation as well as the presentation of an automated proof constructivization algorithm
19
Pandya, Rashmibala. "A multi-layered framework for higher order probabilistic reasoning." Thesis, University of Exeter, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.364432.
Full text
20
Miura, Kinya. "Proof System of Higher-Order Clausal Logic and its Parallel Implementation." Kyoto University, 1995. http://hdl.handle.net/2433/160754.
Full textAbstract:
本文データは平成22年度国立国会図書館の学位論文(博士)のデジタル化実施により作成された画像ファイルを基にpdf変換したものであるKyoto University (京都大学)
0048
新制・論文博士
博士(工学)
乙第8773号
論工博第2935号
新制||工||978(附属図書館)
UT51-95-B238
(主査)教授 堂下 修司, 教授 矢島 脩三, 教授 石田 亨
学位規則第4条第2項該当
21
Martin, Alan J. "Reasoning Using Higher-Order Abstract Syntax in a Higher-Order Logic Proof Environment: Improvements to Hybrid and a Case Study." Thesis, Université d'Ottawa / University of Ottawa, 2010. http://hdl.handle.net/10393/19711.
Full textAbstract:
We present a series of improvements to the Hybrid system, a formal theory implemented in Isabelle/HOL to support specifying and reasoning about formal systems using higher-order abstract syntax (HOAS). We modify Hybrid's type of terms, which is built definitionally in terms of de Bruijn indices, to exclude at the type level terms with `dangling' indices. We strengthen the injectivity property for Hybrid's variable-binding operator, and develop rules for compositional proof of its side condition, avoiding conversion from HOAS to de Bruijn indices. We prove representational adequacy of Hybrid (with these improvements) for a lambda-calculus-like subset of Isabelle/HOL syntax, at the level of set-theoretic semantics and without unfolding Hybrid's definition in terms of de Bruijn indices. In further work, we prove an induction principle that maintains some of the benefits of HOAS even for open terms. We also present a case study of the formalization in Hybrid of a small programming language, Mini-ML with mutable references, including its operational semantics and a type-safety property. This is the largest case study in Hybrid to date, and the first to formalize a language with mutable references. We compare four variants of this formalization based on the two-level approach adopted by Felty and Momigliano in other recent work on Hybrid, with various specification logics (SLs), including substructural logics, formalized in Isabelle/HOL and used in turn to encode judgments of the object language. We also compare these with a variant that does not use an intermediate SL layer. In the course of the case study, we explore and develop new proof techniques, particularly in connection with context invariants and induction on SL statements.
22
Battell, Chelsea. "The Logic of Hereditary Harrop Formulas as a Specification Logic for Hybrid." Thesis, Université d'Ottawa / University of Ottawa, 2016. http://hdl.handle.net/10393/35264.
Full textAbstract:
Hybrid is a two-level logical framework that supports higher-order abstract syntax
(HOAS), where a specification logic (SL) extends the class of object logics (OLs) we
can reason about. We develop a new Hybrid SL and formalize its metatheory, proving weakening, contraction, exchange, and cut admissibility; results that greatly simplify reasoning about OLs in systems providing HOAS. The SL is a sequent calculus defined as an inductive type in Coq and we prove properties by structural induction over SL sequents. We also present a generalized SL and metatheory statement, allowing us to prove many cases of such theorems in a general way and understand how to identify and prove the difficult cases. We make a concrete and measurable improvement to Hybrid with the new SL formalization and provide a technique for abstracting such proofs, leading to a condensed presentation, greater understanding, and a generalization that may be instantiated to other logics.
23
Ng, Kee Siong, and kee siong@rsise anu edu au. "Learning Comprehensible Theories from Structured Data." The Australian National University. Research School of Information Sciences and Engineering, 2005. http://thesis.anu.edu.au./public/adt-ANU20051031.105726.
Full textAbstract:
This thesis is concerned with the problem of
learning comprehensible theories from
structured data and covers primarily classification and regression learning. The basic knowledge representation language
is set around a polymorphically-typed,
higher-order logic. The general setup is closely related to the learning from propositionalized knowledge and learning from interpretations settings in Inductive Logic Programming. Individuals (also called instances) are represented as terms in the logic. A grammar-like construct called a predicate rewrite system is used to define features in the form of predicates that individuals may or may not satisfy. For learning, decision-tree algorithms of various kinds are adopted.¶
The scope of the thesis spans both theory and practice. On the theoretical side, I study in this thesis¶
1. the representational power of different function classes and relationships between them;¶
2. the sample complexity of some commonly-used predicate classes, particularly those involving sets and multisets;¶
3. the computational complexity of various optimization problems associated with learning and algorithms for solving them; and¶
4. the (efficient) learnability of different function classes in the PAC and agnostic PAC models.¶
On the practical side, the usefulness of the learning system developed is demontrated with applications in two important domains:
bioinformatics and intelligent agents. Specifically, the following are covered in this thesis:¶
1. a solution to a benchmark multiple-instance learning problem and some useful lessons that can be drawn from it;¶
2. a successful attempt on a knowledge discovery problem in predictive toxicology, one that can serve as another proof-of-concept that real chemical knowledge can be obtained using symbolic learning;¶
3. a reworking of an exercise in relational reinforcement learning and some new insights and techniques we learned for this interesting problem; and¶
4. a general approach for personalizing
user agents that takes full advantage of symbolic learning.
24
Kotzsch, Hans-Christoph [Verfasser], and Hannes [Akademischer Betreuer] Leitgeb. "Topos semantics for higher-order modal logic / Hans-Christoph Kotzsch ; Betreuer: Hannes Leitgeb." München : Universitätsbibliothek der Ludwig-Maximilians-Universität, 2016. http://d-nb.info/1125883928/34.
Full text
25
Mukhopadhyay, Trisha. "A Flexible, Natural Deduction, Automated Reasoner for Quick Deployment of Non-Classical Logic." Scholar Commons, 2019. https://scholarcommons.usf.edu/etd/7862.
Full textAbstract:
Automated Theorem Provers (ATP) are software programs which carry out inferences over logico-mathematical systems, often with the goal of finding proofs to some given theorem. ATP systems are enormously powerful computer programs, capable of solving immensely difficult problems. Currently, many automated theorem provers exist like E, vampire, SPASS, ACL2, Coq etc. However, all the available theorem provers have some common problems: (1) Current ATP systems tend not to try to find proofs entirely on their own. They need help from human experts to supply lemmas, guide the proof, etc. (2) There is not a single proof system available which provides fully automated platforms for both First Order Logic (FOL) and other Higher Order Logic (HOL). (3) Finally, current proof systems do not have an easy way to quickly deploy and reason over new logical systems, which a logic researcher may want to test.
In response to these problems, I introduce the MATR framework. MATR is a platform-independent, codelet-based (independently operating processes) proof system with an easy-to-use Graphical User Interface (GUI), where multiple codelets can be selected based on the formal system desired. MATR provides a platform for different proof strategies like deduction and backward reasoning, along with different formal systems such as non-classical logics. It enables users to design their own proof system by selecting from the list of codelets without needing to write an ATP from scratch.
26
Atzemoglou, George Philip. "Higher-order semantics for quantum programming languages with classical control." Thesis, University of Oxford, 2012. http://ora.ox.ac.uk/objects/uuid:9fdc4a26-cce3-48ed-bbab-d54c4917688f.
Full textAbstract:
This thesis studies the categorical formalisation of quantum computing, through the prism of type theory, in a three-tier process. The first stage of our investigation involves the creation of the dagger lambda calculus, a lambda calculus for dagger compact categories. Our second contribution lifts the expressive power of the dagger lambda calculus, to that of a quantum programming language, by adding classical control in the form of complementary classical structures and dualisers. Finally, our third contribution demonstrates how our lambda calculus can be applied to various well known problems in quantum computation: Quantum Key Distribution, the quantum Fourier transform, and the teleportation protocol.
27
Reynolds, James. "An automatic proof-generating translation from higher-order to first-order logic : with applications to linking HOL4 and ACL2." Thesis, University of Cambridge, 2009. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.611133.
Full text
28
Kohlhase, Michael [Verfasser]. "A Mechanization of Sorted Higher-Order Logic Based on the Resolution Principle / Michael Kohlhase." Kaiserslautern : Technische Universität Kaiserslautern, Fachbereich Informatik, 1999. http://d-nb.info/1027386598/34.
Full text
29
Bulwahn, Lukas [Verfasser], Tobias [Akademischer Betreuer] Nipkow, and Colin [Akademischer Betreuer] Runciman. "Counterexample Generation for Higher-Order Logic Using Functional and Logic Programming / Lukas Bulwahn. Gutachter: Tobias Nipkow ; Colin Runciman. Betreuer: Tobias Nipkow." München : Universitätsbibliothek der TU München, 2013. http://d-nb.info/1033891142/34.
Full text
30
Sofianatos, Georgios. "Higher order QCD effects for Higgs boson studies at colliders /." May be available electronically:, 2009. http://proquest.umi.com/login?COPT=REJTPTU1MTUmSU5UPTAmVkVSPTI=&clientId=12498.
Full text
31
Böhme, Sascha Verfasser], Tobias [Akademischer Betreuer] [Nipkow, and Andrey [Akademischer Betreuer] Rybalchenko. "Proving Theorems of Higher-Order Logic with SMT Solvers / Sascha Böhme. Gutachter: Andrey Rybalchenko. Betreuer: Tobias Nipkow." München : Universitätsbibliothek der TU München, 2012. http://d-nb.info/1023128497/34.
Full text
32
Kohlhase, Michael [Verfasser], and Jörg [Akademischer Betreuer] Siekmann. "A mechanization of sorted higher-order logic based on the resolution principle / Michael Kohlhase. Betreuer: Jörg Siekmann." Saarbrücken : Saarländische Universitäts- und Landesbibliothek, 2007. http://d-nb.info/1049538501/34.
Full text
33
Carreno, Coll Victor Alberto. "Transition assertions : a higher-order logic based method for the specification and verification of real-time systems." Thesis, University of Cambridge, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.627145.
Full text
34
Wong, Wai. "A formal theory of railway track networks in higher-order logic and its applications in interlocking design." Thesis, University of Warwick, 1992. http://wrap.warwick.ac.uk/110541/.
Full textAbstract:
The research described in this dissertation centres on the application of a discipline of formal methods in railway signalling system design. A generic abstract model of railway track networks and signals has been developed in Higher-Order Logic(HOL). It consists of several theories arranged in a hierarchy. Railway track networks are modelled by a class of constraint labelled directed graphs. HOL theories of graphs and paths have been developed for representing track networks. HOL theories modelling individual track components and signals have also been developed. These theories are then combined to create a theory of track network. Three applications of this model are described. The first is a network verifier which verifies a formal specification of track layout against its abstract model by proving theorems automatically. The second application is to extract information from the specifications and to create control tables automatically. Lastly, a method of modelling the interlocking processor using finite state machines is described. Although this research has centred on railway signalling, it can be viewed as a case study of how to apply formal methods in the analysis and design of safety- critical systems. The approach and methods used can be generalized in order to be useful in other industries.
35
Anglès, d'Auriac Paul-Elliot. "Infinite Computations in Algorithmic Randomness and Reverse Mathematics." Thesis, Paris Est, 2019. http://www.theses.fr/2019PESC0061.
Full textAbstract:
Cette thèse se concentre sur l'apport du calcul en temps infini à la logique mathématique. Le calcul en temps infini est une variante de la traditionnelle définition du calcul comme suite finie d'étapes, chaque étape étant définie à partir des précédentes, et aboutissant à un état final. Dans le cas de cette thèse, nous considérons le cas où le nombre d'étapes n'est pas forcément fini, mais peut continuer le long des ordinaux, une extension des entiers. Il existe plusieurs manières d'implémenter cette idée, nous en utilisons trois : la calculabilité d'ordre supérieur, les machines de Turing à temps infini et l'α-récursion.Une part de ce travail concerne les mathématiques à rebours, et plus particulièrement le théorème de Hindman. Les mathématiques à rebours sont un programme mathématique consistant en l'étude des théorèmes et axiomes mathématiques du point de vue de leur "puissance", et établissant une hiérarchie sur celle-ci. En particulier la détermination des briques de bases, aussi appelées axiomes, qui sont nécessaires dans une preuve est centrale. Nous étudions au travers de ce prisme le théorème de Hindman, un théorème combinatoire de la théorie de Ramsey qui dit que pour tout partitionnement des entiers en un nombre fini d'ensembles, appelés couleurs, il doit exister une ensemble infini S d'entiers dont toute les sommes d'éléments issus de S ont la même couleur. Dans cette thèse, nous progressons dans la résolution de la question du système d'axiomes minimal pour prouver ce théorème, en montrant que l'existence d'objets combinatoires intermédiaires est prouvable dans un système d'axiome faible.La réduction de Weihrauch est une méthode récente de comparaison de puissance de théorème, qui les considère comme des problèmes à résoudre, puis compare leur difficulté. Cette réduction a été moins étudiée, et en particulier certains des principes les plus importants des mathématiques à rebours ne sont pas bien compris dans ce cadre. L'un d'eux est le principe ATR de Récursion Arithmétique Transfinie, un principe très lié au calcul en temps infini et plus particulièrement à la calculabilité d'ordre supérieur. Nous continuons l'étude de ce principe en montrant ses liens avec un type particulier d'axiome du choix, et l'utilisons pour séparer les versions dépendantes et indépendantes de ces axiomes.Un autre domaine de la logique mathématiques qui tire parti de la théorie de la calculabilité est l'aléatoire algorithmique. Ce domaine étudie les réels "aléatoires", c'est à dire ceux dont il paraît raisonnable qu'ils aient été obtenus de façon purement aléatoire. Une manière d'étudier cela est de considérer, étant donné un réel, la plus petite complexité algorithmique d'un ensemble de mesure 0 le contenant. Ce domaine est très riche et a déjà été étendu à certains types de calcul en temps infini, modifiant ainsi les classes de complexité considérées. Cependant, il a seulement très récemment été étendu aux machines de Turing à temps infini (ITTMs) et à l'α-récursion. Dans cette thèse, nous contribuons à l'étude des notions d'aléatoire pour ITTMs et α-récursion les plus naturelles. Nous montrons que deux classes importantes, le Σ-aléatoire et l'ITTM-aléatoire, ne sont pas automatiquement distinctes ; en particulier leurs équivalents catégoriques sont confondusThis thesis focuses on the gains of infinite time computations to mathematical logic. Infinite time computations is a variant of the traditional definition of computations as a finite sequence of stages, each stage being defined from the previous ones, and finally reaching a halting state. In this thesis, we consider the case where the number of stages is not necessarily finite, but can continue along ordinals, an extension of the integers. There exists several ways to implement this idea, we will use three of them: higher recursion, infinite time Turing machines and α-recursion.Part of this works concerns the domain of reverse mathematics, and especially Hindman's theorem. Reverse mathematics is a program consisting in the study of theorems and axioms from the point of view of their "strength", and establishing a hierarchy on these. In particular the question of which axioms are needed in a proof of a given statement is central. We study Hindman's theorem under this lens, a combinatorial result from Ramsey's theory stating that for every partitioning of the integers into finitely many colors, there must exists an infinite set such that any sum of elements taken from it has a fixed color. In this thesis, we make some progress in the question of the minimal axiomatic system needed to show this result, by showing that the existence of some intermediate combinatorial objects is provable in a weak system.Weihrauch reduction is a way to compare the strength of theorems, that has been introduced in reverse mathematics recently. It sees theorems as problems to solve, and then compare their difficulties. This reduction is still less studied in this context, in particular few of the most important principles of reverse mathematics are not yet well comprehended. One of these is the Arithmetical Transfinite Recursion principle, an axiomatic system with strong links with infinite time computations and especially higher recursion. We continue the study of this principle by showing its links with a particular type of axiom of choice, and use it to separate the dependent and independent version of this choice.Yet another field of mathematical logic that benefits from computability theory is the one of algorithmic randomness. It studies "random" reals, those that it would seem reasonable to think that they arise from a process picking a real uniformly in some interval. A way to study this is to considerate, for a given real, the smallest algorithmic complexity of a null set containing it. This domain has proven very rich and has already been extended to certain type of infinite time computation, thereby modifying the complexity class considered. However, it has been extended to infinite time Turing machine and α-recursion only recently, by Carl and Schlicht. In this thesis, we contribute to the study of the most natural randomness classes for ITTMs and α-recursion. We show that two important classes, Σ-randomness and ITTM-randomness, are not automatically different; in particular their categorical equivalent are in fact the same classes
36
Raghunandan, Jayshan. "Curry-Howard Calculi from Classical Logical Connectives : A Generic Tool for Higher-Order Term Graph Rewriting." Thesis, Imperial College London, 2009. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.508781.
Full text
37
Blanchette, Jasmin Christian Verfasser], Tobias [Akademischer Betreuer] [Nipkow, and Koen [Akademischer Betreuer] Claessen. "Automatic Proofs and Refutations for Higher-Order Logic / Jasmin Christian Blanchette. Gutachter: Tobias Nipkow ; Koen Claessen. Betreuer: Tobias Nipkow." München : Universitätsbibliothek der TU München, 2012. http://d-nb.info/1024354997/34.
Full text
38
Blanchette, Jasmin [Verfasser], Tobias [Akademischer Betreuer] Nipkow, and Koen [Akademischer Betreuer] Claessen. "Automatic Proofs and Refutations for Higher-Order Logic / Jasmin Christian Blanchette. Gutachter: Tobias Nipkow ; Koen Claessen. Betreuer: Tobias Nipkow." München : Universitätsbibliothek der TU München, 2012. http://nbn-resolving.de/urn:nbn:de:bvb:91-diss-20120628-1097834-1-6.
Full text
39
Dubcová, Lenka. "Novel self-adaptive higher-order finite elements methods for Maxwell's equations of electromagnetics." To access this resource online via ProQuest Dissertations and Theses @ UTEP, 2008. http://0-proquest.umi.com.lib.utep.edu/login?COPT=REJTPTU0YmImSU5UPTAmVkVSPTI=&clientId=2515.
Full text
40
Wisnesky, Ryan. "Functional Query Languages with Categorical Types." Thesis, Harvard University, 2013. http://dissertations.umi.com/gsas.harvard:11288.
Full textAbstract:
We study three category-theoretic types in the context of functional query languages (typed lambda-calculi extended with additional operations for bulk data processing). The types we study are:Engineering and Applied Sciences
41
Kunčar, Ondřej Verfasser], Tobias [Akademischer Betreuer] [Gutachter] [Nipkow, and Lawrence C. [Gutachter] Paulson. "Types, Abstraction and Parametric Polymorphism in Higher-Order Logic / Ondřej Kunčar. Betreuer: Tobias Nipkow. Gutachter: Lawrence C. Paulson ; Tobias Nipkow." München : Universitätsbibliothek der TU München, 2016. http://d-nb.info/1106382153/34.
Full text
42
Tian, Chun. "A formalization of unique solutions of equations in process algebra." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2017. http://amslaurea.unibo.it/14798/.
Full textAbstract:
In this thesis, a comprehensive formalization of Milner's Calculus of Communicating Systems (also known as CCS) has been done in HOL theorem prover (HOL4), based on an old work in HOL88. This includes all classical properties of strong/weak bisimulation equivalences and observation congruence, a theory of congruence for CCS, various versions of ``bisimulation up to'' techniques, and several deep theorems, namely the ``coarsest congruence contained in weak equivalence'', and three versions of the ``unique solution of equations'' theorem in Milner's book.
This work is further extended to support recent developments in Concurrency Theory, namely the ``contraction'' relation and the related ``unique solutions of contractions'' theorem found by Prof. Davide Sangiorgi, University of Bologna. As a result, a rather complete theory of ``contraction'' (and a similar relation called ``expansion'') for CCS is also formalized in this thesis. Further more, a new variant of contraction called ``observational contraction'' was found by the author during this work, based on existing contraction relation. It's formally proved that, this new relation is preserved by direct sums of CCS processes, and has a more elegant form of the ``unique solutions of contractions'' theorem without any restriction on the CCS grammar.
The contribution of this thesis project is at least threefold: First, it can be seen as a formal verification of the core results in Prof.\ Sangiorgi's paper, and it provides all details for the informal proof sketches given in the paper. Second, a large piece of old proof scripts from the time of Hol88 (1990s) has been ported to HOL4 and made available to all its users. Third, it's a proof engineering research by itself on the correct formalization of process algebra, because the work has made extensive uses of some new features (e.g. coinductive relation) provided in recent versions of HOL4 (Kananaskis-11 and later).
43
Sbardolini, Giorgio. "From Language to Thought: On the Logical Foundations of Semantic Theory." The Ohio State University, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=osu155307880402531.
Full text
44
Bacon, Andrew Jonathan. "Indeterminacy : an investigation into the Soritical and semantical paradoxes." Thesis, University of Oxford, 2012. http://ora.ox.ac.uk/objects/uuid:b4490a8c-0089-4c77-8d24-1ab1ca5baaf0.
Full textAbstract:
According to orthodoxy the study of the Soritical and semantical paradoxes belongs to the domain of the philosophy of language. To solve these paradoxes we need to investigate the nature of words like `heap' and `true.' In this thesis I criticise linguistic explanations of the state of ignorance we find ourselves in when confronted with indeterminate cases and develop a classical non-linguistic theory of indeterminacy in its stead. The view places the study of vagueness and indeterminacy squarely in epistemological terms, situating it within a theory of rational propositional attitudes. The resulting view is applied to a number of problems in the philosophy of vagueness and the semantic paradoxes.
45
Hölzl, Johannes Verfasser], Tobias [Akademischer Betreuer] [Nipkow, and Estaun Francisco Javier [Akademischer Betreuer] Esparza. "Construction and Stochastic Applications of Measure Spaces in Higher-Order Logic / Johannes Hölzl. Gutachter: Tobias Nipkow ; Francisco Javier Esparza Estaun. Betreuer: Tobias Nipkow." München : Universitätsbibliothek der TU München, 2013. http://d-nb.info/1033640344/34.
Full text
46
Worth, Andrew Christopher. "English Coordination in Linear Categorial Grammar." The Ohio State University, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=osu1451933040.
Full text
47
Hague, Matthew. "Saturation methods for global model-checking pushdown systems." Thesis, University of Oxford, 2009. http://ora.ox.ac.uk/objects/uuid:40263ddb-312d-4e18-b774-2caf4def0e76.
Full textAbstract:
Pushdown systems equip a finite state system with an unbounded stack memory, and are thus infinite state. By recording the call history on the stack, these systems provide a natural model for recursive procedure calls. Model-checking for pushdown systems has been well-studied. Tools implementing pushdown model-checking (e.g. Moped) are an essential back-end component of high-profile software model checkers such as SLAM, Blast and Terminator. Higher-order pushdown systems define a more complex memory structure: a higher-order stack is a stack of lower-order stacks. These systems form a robust hierarchy closely related to the Caucal hierarchy and higher-order recursion schemes. This latter connection demonstrates their importance as models for programs with higher-order functions. We study the global model-checking problem for (higher-order) pushdown systems. In particular, we present a new algorithm for computing the winning regions of a parity game played over an order-1 pushdown system. We then show how to compute the winning regions of two-player reachability games over order-n pushdown systems. These algorithms extend the saturation methods of Bouajjani, Esparza and Maler for order-1 pushdown systems, and Bouajjani and Meyer for higher-order pushdown systems with a single control state. These techniques begin with an automaton recognising (higher-order) stacks, and iteratively add new transitions until the automaton becomes saturated. The reachability result, presented at FoSSaCS 2007 and in the LMCS journal, is the main contribution of the thesis. We break the saturation paradigm by adding new states to the automaton during the iteration. We identify the fixed points required for termination by tracking the updates that are applied, rather than by observing the transition structure. We give a number of applications of this result to LTL model-checking, branching-time model-checking, non-emptiness of higher-order pushdown automata and Büchi games. Our second major contribution is the first application of the saturation technique to parity games. We begin with a mu-calculus characterisation of the winning region. This formula alternates greatest and least fixed point operators over a kind of reachability formula. Hence, we can use a version of our reachability algorithm, and modifications of the Büchi techniques, to compute the required result. The main advantages of this approach compared to existing techniques due to Cachat, Serre and Vardi et al. are that it is direct and that it is not immediately exponential in the number of control states, although the worst-case complexity remains the same.
48
Jacinto, Bruno. "Necessitism, contingentism and theory equivalence." Thesis, University of St Andrews, 2016. http://hdl.handle.net/10023/8814.
Full textAbstract:
Two main questions are addressed in this dissertation, namely: 1. What is the correct higher-order modal theory; 2. What does it take for theories to be equivalent. The whole dissertation consists of an extended argument in defence of the joint truth of two higher-order modal theories, namely, Plantingan Moderate Contingentism, a higher-order necessitist theory advocated by Plantinga (1974) and committed to the contingent being of some individuals, and Williamsonian Thorough Necessitism, a higher-order necessitist theory advocated by Williamson (2013) and committed to the necessary being of every possible individual. The case for the truth of these two theories relies on defences of the following metaphysical theses: i) Thorough Serious Actualism, according to which no things could have been related and yet be nothing, ii) Higher-Order Necessitism, according to which necessarily, every higher-order entity is necessarily something. It is shown that Thorough Serious Actualism and Higher-Order Necessitism are both implicit commitments of very weak logical theories. Prima facie, Plantingan Moderate Contingentism and Williamsonian Thorough Necessitism are jointly inconsistent. The argument for their joint truth thus relies also on showing i) their equivalence, and ii) that the dispute between Plantingans and Williamsonians is merely verbal. The case for i) and ii) relies on the Synonymy Account, an account of theory equivalence developed and defended in the dissertation. According to the account, theories are equivalent just in case they have the same structure of entailments and commitments, and the occupiers of the places in that structure are the same propositions. An immediate consequence of the Synonymy Account is that proponents of synonymous theories are engaged in merely verbal disputes. The Synonymy Account is also applied to the debate between noneists and Quineans, revealing that what is in question in that debate is what are the expressive resources available to describe the world.
49
Maffre, Faustine. "Le bonheur est dans l'ignorance : logiques épistémiques dynamiques basées sur l'observabilité et leurs applications." Thesis, Toulouse 3, 2016. http://www.theses.fr/2016TOU30112/document.
Full textAbstract:
Dans les logiques épistémiques, la connaissance est généralement modélisée par un graphe de mondes possibles, qui correspondent aux alternatives à l'état actuel du monde. Ainsi, les arêtes entre les mondes représentent l'indistinguabilité. Connaître une proposition signifie que cette proposition est vraie dans toutes les alternatives possibles. Les informaticiens théoriques ont cependant remarqué que cela a conduit à plusieurs problèmes, à la fois intuitifs et techniques : plus un agent est ignorant, plus elle a d'alternatives à examiner ; les modèles peuvent alors devenir trop grands pour la vérification de système. Ils ont récemment étudié comment la connaissance pourrait être réduite à la notion de visibilité. Intuitivement, l'idée de base est que quand un agent voit quelque chose, alors elle sait sa valeur de vérité. A l'inverse, toute combinaison de valeurs de vérité des variables non observables est possible pour l'agent. Ces informations d'observabilité permettent de reconstituer la sémantique standard de la connaissance : deux mondes sont indistinguables pour un agent si et seulement si chaque variable observée par cet agent a la même valeur dans les deux mondes. Notre objectif est de démontrer que les logiques épistémiques fondées sur la visibilité constituent un outil approprié pour plusieurs applications importantes dans le domaine de l'intelligence artificielle. Dans le cadre actuel de ces logiques de visibilité, chaque agent a un ensemble de variables propositionnelles qu'elle peut observer ; ces visibilités sont constantes à travers le modèle. Cela accompagne une hypothèse forte : les visibilités sont connues de tous, et sont même connaissance commune. De plus, la construction de la connaissance à partir de la visibilité entraîne des validités contre-intuitives, la plus importante étant que l'opérateur de la connaissance distribue sur les disjonctions de littéraux : si un agent sait que p ou q est vrai, alors elle sait que p est vrai ou que q est vrai, parce qu'elle peut les voir. Dans cette thèse, nous proposons des solutions à ces deux problèmes et les illustrons sur diverses applications telles que la planification épistémique ou les jeux booléens épistémiques, et sur des exemples plus spécifiques tels que le problème des enfants sales ou le problème du bavardage. Nous étudions en outre des propriétés formelles des logiques que nous concevons, fournissant axiomatisations et résultats de complexitéIn epistemic logic, knowledge is usually modelled by a graph of possible worlds, representing the alternatives to the current state of the world. So edges between worlds stand for indistinguishability. To know a proposition means that that proposition is true in all possible alternatives. Theoretical computer scientists however noticed that this led to several issues, both intuitively and technically: the more an agent is ignorant, the more alternatives she must consider; models may then become too big for system verification. They recently investigated how knowledge could be reduced to the notion of visibility. Intuitively, the basic idea is that when an agent sees something, then she knows its truth value. The other way round, any combination of truth values of the non-observable variables is possible for the agent. Such observability information allows us to reconstruct the standard semantics of knowledge: two worlds are indistinguishable for an agent if and only if every variable observed by her has the same value in both worlds. We aim to demonstrate that visibility-based epistemic logics provide a suitable tool for several important applications in the field of artificial intelligence. In the current settings of these logics of visibility, every agent has a set of propositional variables that she can observe; these visibilities are constant across the model. This comes with a strong assumption: visibilities are known to everyone, and are even common knowledge. Moreover, constructing knowledge from visibility brings about counter-intuitive validities, the most important being that the knowledge operator distributes over disjunction of literals: if an agent knows that p or q is true, then she knows that p is true or that q is true because she can see them. In this thesis, we propose solutions to these two problems and illustrate them on various applications such as epistemic planning or epistemic boolean games, and on more specific examples such as the muddy children problem or the gossip problem. We moreover study formal properties of the logics we design, providing axiomatizations and complexity results
50
Lundberg, Didrik. "Provably Sound and Secure Automatic Proving and Generation of Verification Conditions." Thesis, KTH, Teoretisk datalogi, TCS, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-239441.
Full textAbstract:
Formal verification of programs can be done with the aid of an interactive theorem prover. The program to be verified is represented in an intermediate language representation inside the interactive theorem prover, after which statements and their proofs can be constructed. This is a process that can be automated to a high degree. This thesis presents a proof procedure to efficiently generate a theorem stating the weakest precondition for a program to terminate successfully in a state upon which a certain postcondition is placed. Specifically, the Poly/ML implementation of the SML metalanguage is used to generate a theorem in the HOL4 interactive theorem prover regarding the properties of a program written in BIR, an abstract intermediate representation of machine code used in the PROSPER project.Bevis av säkerhetsegenskaper hos program genom formell verifiering kan göras med hjälp av interaktiva teorembevisare. Det program som skall verifieras representeras i en mellanliggande språkrepresentation inuti den interaktiva teorembevisaren, varefter påståenden kan konstrueras, som sedan bevisas. Detta är en process som kan automatiseras i hög grad. Här presenterar vi en metod för att effektivt skapa och bevisa ett teorem som visar sundheten hos den svagaste förutsättningen för att ett program avslutas framgångsrikt under ett givet postvillkor. Specifikt använder vi Poly/ML-implementationen av SML för att generera ett teorem i den interaktiva teorembevisaren HOL4 som beskriver egenskaper hos ett program i BIR, en abstrakt mellanrepresentation av maskinkod som används i PROSPER-projektet.