: leaves 122-134 / There have been numerous studies on formal methods but little utilisation of formal methods in the commercial world. This can be attributed to many factors, such as that few specialists know how to use formal methods. Moreover, the use of mathematical notation leads to the perception that formal methods are difficult. Formal methods can be described as system design methods by which complex computer systems are built using mathematical notation and logic. Formal methods have been used in the software development world since 1940, that is to say, from the earliest stage of computer development. To date, there has been a slow adoption of formal methods, which are mostly used for mission-critical projects in, for example, the military and the aviation industry. Researchers worldwide are conducting studies on formal methods, but the research mostly deals with path planning and control and not the runtime verification of autonomous systems. The main focus of this dissertation is the question of how to increase the pace at which formal methods are adopted in the business or commercial world. As part of this dissertation, a framework was developed to facilitate the use of formal methods in the commercial world. The framework mainly focuses on education, support tools, buy-in and remuneration. The framework was validated using a case study to illustrate its practicality. This dissertation also focuses on different types of formal methods and how they are used, as well as the link between formal methods and other software development techniques. An ERP system specification is presented in both natural language (informal) and formal notation, which demonstrates how a formal specification can be derived from an informal specification using the enhanced established strategy for constructing a Z specification as a guideline. Success stories of companies that are applying formal methods in the commercial world are also presented. / School of Computing / M. Sc. (Computing)

Relational data is characterised by the rich structure it encodes in the dependencies between the individual entities of a given domain. Statistical Relational Learning (SRL) combines first-order logic and probability to learn and reason over relational domains by creating parametric probability distributions over relational structures. SRL models can succinctly represent the complex dependencies in relational data and admit learning and inference under uncertainty. However, these models are significantly limited when it comes to the tractability of learning and inference. This limitation emerges from the intractability of Weighted First Order Model Counting (WFOMC), as both learning and inference in SRL models can be reduced to instances of WFOMC. Hence, fragments of first-order logic that admit tractable WFOMC, widely known as domain-liftable, can significantly advance the practicality and efficiency of SRL models. Recent works have uncovered another limitation of SRL models, i.e., they lead to unintuitive behaviours when used across varying domain sizes, violating fundamental consistency conditions expected of sound probabilistic models. Such inconsistencies also mean that conventional machine learning techniques, like training with batched data, cannot be soundly used for SRL models. In this thesis, we contribute to both the tractability and consistency of probabilistic inference in SRL models. We first expand the class of domain-liftable fragments with counting quantifiers and cardinality constraints. Unlike the algorithmic approaches proposed in the literature, we present a uniform combinatorial approach, admitting analytical combinatorial formulas for WFOMC. Our approach motivates a new family of weight functions allowing us to express a larger class of probability distributions without losing domain-liftability. We further expand the class of domain-liftable fragments with constraints inexpressible in first-order logic, namely acyclicity and connectivity constraints. Finally, we present a complete characterization for a statistically consistent (a.k.a projective) models in the two-variable fragment of a widely used class of SRL models, namely Markov Logic Networks.

The Golog action programming language is a powerful means to express high-level behaviours in terms of programs over actions defined in a Situation Calculus theory. In particular for physical systems, verifying that the program satisfies certain desired temporal properties is often crucial, but undecidable in general, the latter being due to the language’s high expressiveness in terms of first-order quantification and program constructs. So far, approaches to achieve decidability involved restrictions where action effects either had to be contextfree (i.e. not depend on the current state), local (i.e. only affect objects mentioned in the action’s parameters), or at least bounded (i.e. only affect a finite number of objects). In this paper, we present a new, more general class of action theories (called acyclic) that allows for context-sensitive, non-local, unbounded effects, i.e. actions that may affect an unbounded number of possibly unnamed objects in a state-dependent fashion. We contribute to the further exploration of the boundary between decidability and undecidability for Golog, showing that for acyclic theories in the two-variable fragment of first-order logic, verification of CTL properties of programs over ground actions is decidable.

Ontology-based data access (OBDA) generalizes query answering in relational databases. It allows to query a database by using the language of an ontology, abstracting from the actual relations of the database. For ontologies formulated in Description Logics of the DL-Lite family, OBDA can be realized by rewriting the query into a classical first-order query, e.g. an SQL query, by compiling the information of the ontology into the query. The query is then answered using classical database techniques. In this report, we consider a temporal version of OBDA. We propose a temporal query language that combines a linear temporal logic with queries over DL-Litecore-ontologies. This language is well-suited for expressing temporal properties of dynamical systems and is useful in context-aware applications that need to detect specific situations. Using a first-order rewriting approach, we transform our temporal queries into queries over a temporal database. We then present three approaches to answering the resulting queries, all having different advantages and drawbacks. / This revised version proves that the presented algorithm achieves a bounded history encoding.

Text in English with abstracts in English, Afrikaans and isiZulu / The formalisation of first-order logic and axiomatic set theory in the first half of the 20th century—along with the advent of the digital computer—paved the way for the development of automated theorem proving. In the 1950s, the automation of proof developed from proving elementary geometric problems and finding direct proofs for problems in Principia Mathematica by means of simple, human-oriented rules of inference. A major advance in the field of automated theorem proving occurred in 1965, with the formulation of the resolution inference mechanism. Today, powerful Satisfiability Modulo Theories (SMT) provers combine SAT solvers with sophisticated knowledge from various problem domains to prove increasingly complex theorems. The combinatorial explosion of the search space is viewed as one of the major challenges to progress in the field of automated theorem proving. Pioneers from the 1950s and 1960s have already identified the need for heuristics to guide the proof search effort. Despite theoretical advances in automated reasoning and technological advances in computing, the size of the search space remains problematic when increasingly complex proofs are attempted. Today, heuristics are still useful and necessary to discharge complex proof obligations. In 2000, a number of heuristics was developed to aid the resolution-based prover OTTER in finding proofs for set-theoretic problems. The applicability of these heuristics to next-generation theorem provers were evaluated in 2009. The provers Vampire and Gandalf required respectively 90% and 80% of the applicable OTTER heuristics. This dissertation investigates the applicability of the OTTER heuristics to theorem proving in the hybrid theorem proving environment Rodin—a system modelling tool suite for the Event-B formal method. We show that only 2 of the 10 applicable OTTER heuristics were useful when discharging proof obligations in Rodin. Even though we argue that the OTTER heuristics were largely ineffective when applied to Rodin proofs, heuristics were still needed when proof obligations could not be discharged automatically. Therefore, we propose a number of our own heuristics targeted at theorem proving in the Rodin tool suite. / Die formalisering van eerste-orde-logika en aksiomatiese versamelingsteorie in die eerste helfte van die 20ste eeu, tesame met die koms van die digitale rekenaar, het die weg vir die ontwikkeling van geoutomatiseerde bewysvoering gebaan. Die outomatisering van bewysvoering het in die 1950’s ontwikkel vanuit die bewys van elementêre meetkundige probleme en die opspoor van direkte bewyse vir probleme in Principia Mathematica deur middel van eenvoudige, mensgerigte inferensiereëls. Vooruitgang is in 1965 op die gebied van geoutomatiseerde bewysvoering gemaak toe die resolusie-inferensie-meganisme geformuleer is. Deesdae kombineer kragtige Satisfiability Modulo Theories (SMT) bewysvoerders SAT-oplossers met gesofistikeerde kennis vanuit verskeie probleemdomeine om steeds meer komplekse stellings te bewys. Die kombinatoriese ontploffing van die soekruimte kan beskou word as een van die grootste uitdagings vir verdere vooruitgang in die veld van geoutomatiseerde bewysvoering. Baanbrekers uit die 1950’s en 1960’s het reeds bepaal dat daar ’n behoefte is aan heuristieke om die soektog na bewyse te rig. Ten spyte van die teoretiese vooruitgang in outomatiese bewysvoering en die tegnologiese vooruitgang in die rekenaarbedryf, is die grootte van die soekruimte steeds problematies wanneer toenemend komplekse bewyse aangepak word. Teenswoordig is heuristieke steeds nuttig en noodsaaklik om komplekse bewysverpligtinge uit te voer. In 2000 is ’n aantal heuristieke ontwikkel om die resolusie-gebaseerde bewysvoerder OTTER te help om bewyse vir versamelingsteoretiese probleme te vind. Die toepaslikheid van hierdie heuristieke vir die volgende generasie bewysvoerders is in 2009 geëvalueer. Die bewysvoerders Vampire en Gandalf het onderskeidelik 90% en 80% van die toepaslike OTTER-heuristieke nodig gehad. Hierdie verhandeling ondersoek die toepaslikheid van die OTTER-heuristieke op bewysvoering in die hibriede bewysvoeringsomgewing Rodin—’n stelselmodelleringsuite vir die formele Event-B-metode. Ons toon dat slegs 2 van die 10 toepaslike OTTER-heuristieke van nut was vir die uitvoering van bewysverpligtinge in Rodin. Ons voer aan dat die OTTER-heuristieke grotendeels ondoeltreffend was toe dit op Rodin-bewyse toegepas is. Desnieteenstaande is heuristieke steeds nodig as bewysverpligtinge nie outomaties uitgevoer kon word nie. Daarom stel ons ’n aantal van ons eie heuristieke voor wat in die Rodin-suite aangewend kan word. / Ukwenziwa semthethweni kwe-first-order logic kanye ne-axiomatic set theory ngesigamu sokuqala sekhulunyaka lama-20—kanye nokufika kwekhompyutha esebenza ngobuxhakaxhaka bedijithali—kwavula indlela ebheke ekuthuthukisweni kwenqubo-kusebenza yokufakazela amathiyoremu ngekhomyutha. Ngeminyaka yawo-1950, ukuqinisekiswa kobufakazi kwasuselwa ekufakazelweni kwezinkinga zejiyomethri eziyisisekelo kanye nasekutholakaleni kobufakazi-ngqo bezinkinga eziphathelene ne-Principia Mathematica ngokuthi kusetshenziswe imithetho yokuqagula-sakucabangela elula, egxile kubantu. Impumelelo enkulu emkhakheni wokufakazela amathiyoremu ngekhompyutha yenzeka ngowe-1965, ngokwenziwa semthethweni kwe-resolution inference mechanism. Namuhla, abafakazeli abanohlonze bamathiyori abizwa nge-Satisfiability Modulo Theories (SMT) bahlanganisa ama-SAT solvers nolwazi lobungcweti oluvela kwizizinda zezinkinga ezihlukahlukene ukuze bakwazi ukufakazela amathiyoremu okungelula neze ukuwafakazela. Ukukhula ngesivinini kobunzima nobunkimbinkimbi benkinga esizindeni esithile kubonwa njengenye yezinselelo ezinkulu okudingeka ukuthi zixazululwe ukuze kube nenqubekela phambili ekufakazelweni kwamathiyoremu ngekhompyutha. Amavulandlela eminyaka yawo-1950 nawo-1960 asesihlonzile kakade isidingo sokuthi amahuristikhi (heuristics) kube yiwona ahola umzamo wokuthola ubufakazi. Nakuba ikhona impumelelo esiyenziwe kumathiyori ezokucabangela okujulile kusetshenziswa amakhompyutha kanye nempumelelo yobuchwepheshe bamakhompyutha, usayizi wesizinda usalokhu uyinkinga uma kwenziwa imizamo yokuthola ubufakazi obuyinkimbinkimbi futhi obunobunzima obukhudlwana. Namuhla imbala, amahuristikhi asewuziso futhi ayadingeka ekufezekiseni izibopho zobufakazi obuyinkimbinkimbi. Ngowezi-2000, kwathuthukiswa amahuristikhi amaningana impela ukuze kulekelelwe uhlelo-kusebenza olungumfakazeli osekelwe phezu kwesixazululo, olubizwa nge-OTTER, ekutholeni ubufakazi bama-set-theoretic problems. Ukusebenziseka kwalawa mahuristikhi kwizinhlelo-kusebenza ezingabafakazeli bamathiyoremu besimanjemanje kwahlolwa ngowezi-2009. Uhlelo-kusebenza olungumfakazeli, olubizwa nge-Vampire kanye nalolo olubizwa nge-Gandalf zadinga ama-90% kanye nama-80%, ngokulandelana kwazo, maqondana nama-OTTER heuristics afanelekile. Lolu cwaningo luphenya futhi lucubungule ukusebenziseka kwama-OTTER heuristics ekufakazelweni kwamathiyoremu esimweni esiyinhlanganisela sokufakazela amathiyoremu esibizwa nge-Rodin—okuyi-system modelling tool suite eqondene ne-Event-B formal method. Kulolu cwaningo siyabonisa ukuthi mabili kuphela kwayi-10 ama-OTTER heuristics aba wusizo ngenkathi kufezekiswa isibopho sobufakazi ku-Rodin. Nakuba sibeka umbono wokuthi esikhathini esiningi ama-OTTER heuristics awazange abe wusizo uma esetshenziswa kuma-Rodin proofs, amahuristikhi asadingeka ezimweni lapho izibopho zobufakazi zingazenzekelanga ngokwazo ngokulawulwa yizinhlelo-kusebenza zekhompyutha. Ngakho-ke, siphakamisa amahuristikhi ethu amaningana angasetshenziswa ekufakazeleni amathiyoremu ku-Rodin tool suite. / School of Computing / M. Sc. (Computer Science)

In this thesis, we study advanced reasoning about dynamical systems in a logical framework -- the situation calculus. In particular, we consider promoting the efficiency of reasoning about action in the situation calculus from three different aspects. First, we propose a modified situation calculus based on the two-variable predicate logic with counting quantifiers. We show that solving the projection and executability problems via regression in such language are decidable. We prove that generally these two problems are co-NExpTime-complete in the modified language. We also consider restricting the format of regressable formulas and basic action theories (BATs) further to gain better computational complexity for reasoning about action via regression. We mention possible applications to formalization of Semantic Web services. Then, we propose a hierarchical representation of actions based on the situation calculus to facilitate development, maintenance and elaboration of very large taxonomies of actions. We show that our axioms can be more succinct, while still using an extended regression operator to solve the projection problem. Moreover, such representation has significant computational advantages. For taxonomies of actions that can be represented as finitely branching trees, the regression operator can sometimes work exponentially faster with our theories than it works with the BATs current situation calculus. We also propose a general guideline on how a taxonomy of actions can be constructed from the given set of effect axioms. Finally, we extend the current situation calculus with the order-sorted logic. In the new formalism, we add sort theories to the usual initial theories to describe taxonomies of objects. We then investigate what is the well-sortness for BATs under such framework. We consider extending the current regression operator with well-sortness checking and unification techniques. With the modified regression, we gain computational efficiency by terminating the regression earlier when reasoning tasks are ill-sorted and by reducing the search spaces for well-sorted objects. We also study that the connection between the order-sorted situation calculus and the current situation calculus.

Dans la première partie de ce manuscrit nous étudions les fonctions rationnelles, c'est-à-dire définies par des transducteurs unidirectionnels. Notre objectif est d'étendre aux transductions les nombreuses correspondances logique-algèbre qui ont été établies concernant les langages, notamment le célèbre théorème de Schützenberger-McNaughton-Papert. Dans le cadre des fonctions rationnelles sur les mots finis, nous obtenons une caractérisation à la Myhill-Nerode en termes de congruences d'indice fini. Cette caractérisation nous permet d'obtenir un résultat de transfert, à partir d'équivalences logique-algèbre pour les langages vers des équivalences pour les transductions. En particulier nous montrons comment décider si une fonction rationnelle est définissable en logique du premier ordre. Sur les mots infinis, nous pouvons également décider la définissabilité en logique du premier ordre, mais avec des résultats moins généraux.Dans la seconde partie nous introduisons une logique pour les transductions et nous résolvons le problème de synthèse régulière : étant donnée une formule de la logique, peut-on obtenir un transducteur bidirectionnel déterministe satisfaisant la formule ? Les fonctions réalisées par des transducteurs bidirectionnels déterministes sont caractérisés par plusieurs modèles différents, y compris par les transducteurs MSO, et ont ainsi été nommées transductions régulières. Plus précisément nous fournissons un algorithme qui produit toujours une fonction régulière satisfaisant une spécification donnée en entrée.Nous exposons également un lien intéressant entre les transductions et les mots avec données. Par conséquent nous obtenons une logique expressive pour les mots avec données, pour laquelle le problème de satisfiabilité est décidable. / In the first part of this manuscript we focus on the study of rational functions, functions defined by one-way transducers.Our goal is to extend to transductions the many logic-algebra correspondences that have been established for languages, such as the celebrated Schützenberger-McNaughton-Papert Theorem. In the case of rational functions over finite words, we obtain a Myhill-Nerode-like characterization in terms of congruences of finite index. This characterization allows us to obtain a transfer result from logic-algebra equivalences for languages to logic-algebra equivalences for transductions. In particular, we show that one can decide if a rational function can be defined in first-order logic.Over infinite words, we obtain weaker results but are still able to decide first-order definability.In the second part we introduce a logic for transductions and solve the regular synthesis problem: given a formula in the logic, can we obtain a two-way deterministic transducer satisfying the formula?More precisely, we give an algorithm that always produces a regular function satisfying a given specification.We also exhibit an interesting link between transductions and words with ordered data. Thus we obtain as a side result an expressive logic for data words with decidable satisfiability.

Made available in DSpace on 2016-04-27T17:27:11Z (GMT). No. of bitstreams: 1 Cassia Sampaio Sanctos.pdf: 875084 bytes, checksum: 3baa23ce43e41c748fa70bf983f30e20 (MD5) Previous issue date: 2015-05-11 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The thesis constitutes a critical review of Gödel´s doctoral dissertation which presents a proof for the completeness of first order logic. The introduction addresses the concepts of formalism, axiomatic method and completeness, thus the proof can be contextualized. The language for the restricted functional calculus is defined, with the corresponding syntax and semantics, and the original Gödel´s demonstration is updated. The appendix contains a translation of the referred dissertation, which is unprecedented in Portuguese / O trabalho constitui um comentário crítico da dissertação de doutorado de Gödel que apresenta uma prova de completude da lógica de primeira ordem. A introdução trata dos conceitos de formalismo, método axiomático e completude, para que seja possível contextualizar a prova. A linguagem para o cálculo funcional restrito é definida, com sua sintaxe e semântica, e a demonstração original de Gödel é atualizada. O apêndice contém a tradução da referida dissertação, que é inédita em língua portuguesa

An abstract knowledge representation of cognitive robots - as used for reasoning and planning - typically relies on symbols denoting objects of the world and states of affairs. The process of creating and maintaining the correct connection between a symbol denoting an object and its corresponding perceptual image (called percept), both referring to the same physical object, is called symbol anchoring. Most current cognitive systems implement an ad hoc solution which may work for the specific, intended application under certain conditions. Conversely, we suggest a formal and general approach to the symbol anchoring problem, which enhances previous approaches in terms of flexibility, applicability and expressiveness, and which completely automates the process of determining and maintaining all plausible hypotheses of correspondences between object symbols and perceptual images of physical objects. Based on the first-order logical Fluent Calculus, our approach inherits its rich expressiveness with respect to knowledge representation and reasoning. Implementing all required symbol anchoring functionalities, our approach also complies with fundamental concepts of phenomenalism, representationalism and the sense-data theory of philosophy of cognition.

In this thesis, we study advanced reasoning about dynamical systems in a logical framework -- the situation calculus. In particular, we consider promoting the efficiency of reasoning about action in the situation calculus from three different aspects. First, we propose a modified situation calculus based on the two-variable predicate logic with counting quantifiers. We show that solving the projection and executability problems via regression in such language are decidable. We prove that generally these two problems are co-NExpTime-complete in the modified language. We also consider restricting the format of regressable formulas and basic action theories (BATs) further to gain better computational complexity for reasoning about action via regression. We mention possible applications to formalization of Semantic Web services. Then, we propose a hierarchical representation of actions based on the situation calculus to facilitate development, maintenance and elaboration of very large taxonomies of actions. We show that our axioms can be more succinct, while still using an extended regression operator to solve the projection problem. Moreover, such representation has significant computational advantages. For taxonomies of actions that can be represented as finitely branching trees, the regression operator can sometimes work exponentially faster with our theories than it works with the BATs current situation calculus. We also propose a general guideline on how a taxonomy of actions can be constructed from the given set of effect axioms. Finally, we extend the current situation calculus with the order-sorted logic. In the new formalism, we add sort theories to the usual initial theories to describe taxonomies of objects. We then investigate what is the well-sortness for BATs under such framework. We consider extending the current regression operator with well-sortness checking and unification techniques. With the modified regression, we gain computational efficiency by terminating the regression earlier when reasoning tasks are ill-sorted and by reducing the search spaces for well-sorted objects. We also study that the connection between the order-sorted situation calculus and the current situation calculus.