This thesis describes a decision and minimization procedure for modal logic. The decision procedure answers the question of whether there exists a satisfying pointed model for a formula which obeys user-specified first-order conditions on the underlying frame. Then the minimization procedure produces a minimal model with respect to the number of worlds that satisfies the desired formula while obeying the requisite conditions on the underlying frame. A proof of correctness for the decision and minimization procedures is supplied, as well as a description of an implementation built upon the Enfragmo model expansion solver. / Graduate / 0984 / 0318 / wbkboyer@gmail.com

Les solveurs SMT sont des outils dédiés à la vérification d'un ensemble de formules mathématiques, en général sans quantificateurs, utilisant un certain nombre de théories prédéfinies, telles que la congruence, l'arithmétique linéaire sur les entiers, les rationnels ou les réels, les tableaux de bits ou les tableaux. Ajouter une nouvelle théorie à un solveur SMT nécessite en général une connaissance assez profonde du fonctionnement interne du solveur, et, de ce fait, ne peut en général être exécutée que par ses développeurs. Pour de nombreuses théories, il est également possible de fournir une axiomatisation finie en logique du premier ordre. Toutefois, si les solveurs SMT sont généralement complets et efficaces sur des problèmes sans quantificateurs, ils deviennent imprévisibles en logique du premier ordre. Par conséquent, cette approche ne peut pas être utilisée pour fournir une procédure de décision pour ces théories. Dans cette thèse, nous proposons un cadre d'application permettant de résoudre ce problème en utilisant des déclencheurs. Les déclencheurs sont des annotations permettant de spécifier la forme des termes avec lesquels un quantificateur doit être instancié pour obtenir des instances utiles pour la preuve. Ces annotations sont utilisées par la majorité des solveurs SMT supportant les quantificateurs et font partie du format SMT-LIB v2. Dans notre cadre d'application, l'utilisateur fournit une axiomatisation en logique du premier ordre de sa théorie, ainsi qu'une démonstration de sa correction, de sa complétude et de sa terminaison, et obtient en retour un solveur correct, complet et qui termine pour sa théorie. Dans cette thèse, nous décrivons comment un solveur SMT peut être étendu à notre cadre nous basant sur l'algorithme DPLL modulo théories, utilisé traditionnellement pour modéliser ls solveurs SMT. Nous prouvons également que notre extension a bien les propriétés attendues. L'effort à fournir pour implémenter cette extension dans un solveur SMT existant ne doit être effectué qu'une fois et le mécanisme peut ensuite être utilisé sur de multiples théories axiomatisées. De plus, nous pensons que, en général, cette implémentation n'est pas plus compliquée que l'ajout d'une unique théorie au solveur. Nous avons fait ce travail pour le solveur SMT Alt-Ergo, nous en présentons certains détails dans la thèse. Pour valider l'utilisabilité de notre cadre d'application, nous avons prouvé la complétude et la terminaison de plusieurs axiomatizations, dont une pour les listes impératives doublement chaînée, une pour les ensembles applicatifs et une pour les vecteurs de Ada. Nous avons ensuite utilisé notre implémentation dans Alt-Ergo pour discuter de l’efficacité de notre système dans différents cas. / SMT solvers are efficient tools to decide the satisfiability of ground formulas, including a number of built-in theories such as congruence, linear arithmetic, arrays, and bit-vectors. Adding a theory to that list requires delving into the implementation details of a given SMT solver, and is done mainly by the developers of the solver itself. For many useful theories, one can alternatively provide a first-order axiomatization. However, in the presence of quantifiers, SMT solvers are incomplete and exhibit unpredictable behavior. Consequently, this approach can not provide us with a complete and terminating treatment of the theory of interest. In this thesis, we propose a framework to solve this problem, based on the notion of instantiation patterns, also known as triggers. Triggers are annotations that suggest instances which are more likely to be useful in proof search. They are implemented in all SMT solvers that handle first-order logic and are included in the SMT-LIB format. In our framework, the user provides a theory axiomatization with triggers, along with a proof of completeness and termination properties of this axiomatization, and obtains a sound, complete, and terminating solver for her theory in return. We describe and prove a corresponding extension of the traditional Abstract DPLL Modulo Theory framework. Implementing this mechanism in a given SMT solver requires a one-time development effort. We believe that this effort is not greater than that of adding a single decision procedure to the same SMT solver. We have implemented the proposed extension in the Alt-Ergo prover and we discuss some implementation details in the thesis. To show that our framework can handle complex theories, we prove completeness and termination of three axiomatization, one for doubly-linked lists, one for applicative sets, and one for Ada's vectors. Our tests show that, when the theory is heavily used, our approach results in a better performance of the solver on goals that stem from the verification of programs manipulating these data-structures.

<p>The subject of this thesis is ethical aspects of risk management. It is argued that a model for risk management needs to be developed that acknowledges several ethical aspects and most crucial among these, the individual’s right not to be unfairly exposed to risks.</p><p><i>Article </i>I takes as its starting point the demand frequently expressed in the risk literature for a consistent risk management. Such consistency is often assumed to be in accordance with some kind of cost-benefit analysis. It is maintained that such a model, here called the Standard Model, does not respect the rights of the individual. Two alternative models are outlined in order to better deal with this ethical weakness, the Model of Inviolable Rights and the Model of Procedural Justice. The arguments in the alternative models evolve around the separateness of individuals, rights and fair risk taking. It is claimed that the latter model, which focuses on a fair procedure, seems most fruitful to develop.</p><p><i>Article II</i> is a discussion of the NIMBY (Not In My Backyard) conflict, which is well known from situations of siting potentially risky facilities. Of special concern is to investigate what the ethical premises are behind the negative characterization of the NIMBY concept. It is argued that, contrary to the assumption that the total benefit should outweigh the individual’s cost, individuals in siting scenarios have rights not to be unfairly exposed to risks.</p><p><i>Article III</i>, which is co-authored with Professor Sven Ove Hansson, presents a three party model as a tool for ethical risk analysis. It is argued that ethical dimensions need to be acknowledged in the analysis of risks and that this is best done through a discussion of three parties that are involved in risk decisions – the risk-exposed, the beneficiary, and the decisionmaker. Seven crucial ethical questions are recognized and discussed regarding the relation between these parties. By using examples from the railway sector it is shown how the questions can be used to identify salient ethical features of risk management problems.</p>

Automated proof system for logic of correlated knowledge is presented in the dissertation. The system consists of the sequent calculus GS-LCK and the proof search procedure GS-LCK-PROC. Sequent calculus is sound, complete and satisfy the properties of invertibility of rules, admissibility of weakening, contraction and cut. The procedure GS-LCK-PROC is terminating and allows to check if the sequent is provable. Also decidability of logic of correlated knowledge has been proved. Using the terminating procedure GS-LCK-PROC the validity of all formulas of logic of correlated knowledge can be checked. / Automatinė įrodymų sistema koreliatyvių žinių logikai yra pristatoma disertacijoje. Sistemą sudaro sekvencinis skaičiavimas GS-LCK ir įrodymo paieškos procedūra GS-LCK-PROC. Sekvencinis skaičiavimas yra pagrįstas, pilnas ir tenkina taisyklių apverčiamumo, silpninimo, prastinimo ir pjūvio leistinumo savybes. Procedūra GS-LCK-PROC yra baigtinė ir leidžia patikrinti, ar sekvencija yra išvedama. Taip pat buvo įrodytas koreliatyvių žinių logikos išsprendžiamumas. Naudojant baigtinę procedūra GS-LCK-PROC, visų koreliatyvių žinių logikos formulių tapatus teisingumas gali būti patikrintas.

Made available in DSpace on 2014-12-17T15:47:48Z (GMT). No. of bitstreams: 1 DiegoCBO.pdf: 564820 bytes, checksum: eedd81c1881d60fea03c3dcdd8556734 (MD5) Previous issue date: 2007-11-07 / O m?todo de combina??o de Nelson-Oppen permite que v?rios procedimentos de decis?o, cada um projetado para uma teoria espec?&#64257;ca, possam ser combinados para inferir sobre teorias mais abrangentes, atrav?s do princ?pio de propaga??o de igualdades. Provadores de teorema baseados neste modelo s?o bene&#64257;ciados por sua caracter?stica modular e podem evoluir mais facilmente, incrementalmente. Di&#64256;erence logic ? uma subteoria da aritm?tica linear. Ela ? formada por constraints do tipo x &#8722; y &#8804; c, onde x e y s?o vari?veis e c ? uma constante. Di&#64256;erence logic ? muito comum em v?rios problemas, como circuitos digitais, agendamento, sistemas temporais, etc. e se apresenta predominante em v?rios outros casos. Di&#64256;erence logic ainda se caracteriza por ser modelada usando teoria dos grafos. Isto permite que v?rios algoritmos e&#64257;cientes e conhecidos da teoria de grafos possam ser utilizados. Um procedimento de decis?o para di&#64256;erence logic ? capaz de induzir sobre milhares de constraints. Um procedimento de decis?o para a teoria de di&#64256;erence logic tem como objetivo principal informar se um conjunto de constraints de di&#64256;erence logic ? satisfat?vel (as vari?veis podem assumir valores que tornam o conjunto consistente) ou n?o. Al?m disso, para funcionar em um modelo de combina??o baseado em Nelson-Oppen, o procedimento de decis?o precisa ter outras funcionalidades, como gera??o de igualdade de vari?veis, prova de inconsist?ncia, premissas, etc. Este trabalho apresenta um procedimento de decis?o para a teoria de di&#64256;erence logic dentro de uma arquitetura baseada no m?todo de combina??o de Nelson-Oppen. O trabalho foi realizado integrando-se ao provador haRVey, de onde foi poss?vel observar o seu funcionamento. Detalhes de implementa??o e testes experimentais s?o relatados

The subject of this thesis is ethical aspects of risk management. It is argued that a model for risk management needs to be developed that acknowledges several ethical aspects and most crucial among these, the individual’s right not to be unfairly exposed to risks. Article I takes as its starting point the demand frequently expressed in the risk literature for a consistent risk management. Such consistency is often assumed to be in accordance with some kind of cost-benefit analysis. It is maintained that such a model, here called the Standard Model, does not respect the rights of the individual. Two alternative models are outlined in order to better deal with this ethical weakness, the Model of Inviolable Rights and the Model of Procedural Justice. The arguments in the alternative models evolve around the separateness of individuals, rights and fair risk taking. It is claimed that the latter model, which focuses on a fair procedure, seems most fruitful to develop. Article II is a discussion of the NIMBY (Not In My Backyard) conflict, which is well known from situations of siting potentially risky facilities. Of special concern is to investigate what the ethical premises are behind the negative characterization of the NIMBY concept. It is argued that, contrary to the assumption that the total benefit should outweigh the individual’s cost, individuals in siting scenarios have rights not to be unfairly exposed to risks. Article III, which is co-authored with Professor Sven Ove Hansson, presents a three party model as a tool for ethical risk analysis. It is argued that ethical dimensions need to be acknowledged in the analysis of risks and that this is best done through a discussion of three parties that are involved in risk decisions – the risk-exposed, the beneficiary, and the decisionmaker. Seven crucial ethical questions are recognized and discussed regarding the relation between these parties. By using examples from the railway sector it is shown how the questions can be used to identify salient ethical features of risk management problems. / QC 20101116

Tableau-based decision procedures have been successfully used for solving a wide variety of problems. For some applications, nonetheless, it is desirable not only to obtain a Boolean answer, but also to detect the causes for such a result. In this report, a method for finding explanations on tableau-based procedures is explored, generalizing previous results on the field. The importance and use of the method is shown by means of examples.

Motivated by medical terminology applications, we investigate the decidability of an expressive and prominent DL, SHIQ, extended with role inclusion axioms of the form RoS⊑T. It is well-known that a naive such extension leads to undecidability, and thus we restrict our attention to axioms of the form RoS⊑R or SoR⊑R, which is the most important form of axioms in the applications that motivated this extension. Surprisingly, this extension is still undecidable. However, it turns out that restricting our attention further to acyclic sets of such axioms, we regain decidability. We present a tableau-based decision procedure for this DL and report on its implementation, which behaves well in practise and provides important additional functionality in a medical terminology application.

Untersucht wurde die Auseinandersetzung um das Autobahnbauvorhaben A 17 Dresden - Prag zwischen 1990 und 1995 als ein Beispiel der Stadtentwicklung Dresdens. Seit 1935 als Reichsautobahn ins Sudetenland geplant, sollte dieses Verkehrsprojekt nach 1990 als „Lückenschluß im europäischen Autobahnnetz“ umgesetzt werden. Angesichts des hohen Konfliktpotentials erlangte der Fall überregionale Aufmerksamkeit und Beispielcharakter für die neuen Bundesländer. Die Kontroverse gipfelte im ersten Bürgerentscheid der Geschichte Dresdens im Jahre 1995. Das Entscheidungsprocedere wurde erstmals anhand der Theorie des Entscheidungsautismus (SCHULZ-HARDT, 1996) dargestellt. Daraus abgeleitet werden Wege zur Reduzierung von dessen Defiziten aufgezeigt. Dieser Fall wurde dazu aus umwelt-, sozial- und entscheidungspsychologischer Sicht im Hinblick auf die Repräsentation in verschiedenen gesellschaftlichen Gruppen, auf den politischen Kontext und die Partizipationsmöglichkeiten analysiert. Im Mittelpunkt standen dabei Strategien, Handlungsspielräume und Interessen sowie Werte- und Motivstrukturen beteiligter Entscheidungsträger. Die zugrundeliegenden gesellschaftlichen Veränderungen mit ihren Auswirkungen auf die Stadt- und Verkehrsplanung spiegelten Visionen, Interessenlagen und Machtverhältnisse wider und ermöglichten Rückschlüsse auf das Demokratie-, Stadt- und Naturverständnis der jeweiligen Akteure. Für den auf Übertragbarkeit zielenden Forschungsansatz hinsichtlich komplexer und folgenreicher Entscheidungsprozesse erwiesen sich Dresdner Beispiele als besonders geeignet, weil man hier auf eine fast mythologisch erscheinende Verklärung der Stadt und ihrer Geschichte trifft. Sie ist bis heute mit einer engagierten Anteilnahme der Bevölkerung an Stadtentwicklungsprozessen verknüpft. Nach der den Ruf einer europäischen Kunstmetropole begründenden Augustäischen Epoche (1694-1763) verlief die Großstadtwerdung dank vorbildlicher Bauordnungen relativ geordnet. Neben der hohen Baukultur sorgte die oft ideal wirkende Einbeziehung der Landschaft für das „Gesamtkunstwerk Dresden“. Ein Großteil dessen ging 1945 unter. Der Neuaufbau als sozialistische Stadt veränderte nahezu alles, was überkommen war. Dieses zweite Verlusttrauma bestimmt bis heute die Streitkultur im „Dresdner Bürgerinitiativen-Biotop“. Komplexität, Historizität sowie die Extraktion und Synthese interdisziplinärer Gegenstände in dieser Arbeit erforderten die Verwendung des qualitativen Forschungsansatzes unter besonderer Verwendung des Ansatzes des behavior setting (BARKER, 1975) und der qualitativen Inhaltsanalyse (MAYRING, 1990). In der deutschen Tradition der Thematisierung kommunaler Entscheidungsprozesse in der lokalen Politikforschung stehend, konnten mit der literaturgestützten Annäherung aus Gebieten der Umwelt- und Entscheidungspsychologie, der Politikwissenschaft, Stadtökologie und des Verkehrs die wesentlichen Facetten und Perspektiven konfliktträchtigen Entscheidens im städtischen Kontext dargestellt werden. / In the work at hand, the controversial about the construction project of the motorway A17 from Dresden to Prague from 1990 to 1995 is investigated as an examplification for the urban evolution of the city of Dresden. Planned as German Reichsautobahn into the region of Sudeten Germany since 1935, this project was to be realised after 1990 as a “gap closing in the European motorway net”. Due to its high potential for conflicts, this project obtained supra-regional attention and became an example for the German New Laender. In 1995 the controvery culminated in the first referendum in the history of Dresden. This decision procedure was referred to the theory of “Entscheidungsautismus” (SCHULZ-HARDT, 1996). Based on this thesis, the present work will derive strategies concerning the reduction of its deficiencies. Moreover, this subject matter was analysed from an environmental, social and psychological point of view, taking into consideration its political context, how the case was represented in various relevant social groups and which opportunities of social participation the respective groups had. At this point, the strategies, latitudes of action, interests, values and motivation of the involved decision makers were in the centre of consideration. The underlying social reformations with their effects on urban and transport planning reflected perspectives, visions, interests and power structures, and thus enabled conclusions to the democratic, urban and environmental consciousness of the respective protagonists. Due to the almost mythological transfiguration of the city and its history, which, until this day, is connected to a dedicated commitment of the citizens for developmental processes of Dresden, this example from Dresden proved to be especially appropriate concerning its applicability of the scientific approach. After the Augustäische Epoche (1694- 1763) in which Dresden´s reputation as a European metropolis of fine arts was established, the creation of a major city proceeded relatively systematic, owing to an exemplary building regulation. The sophisticated architectural culture and the most of the times ideally inclusion of the surrounding nature lead to the holistic artwork Dresden used to be, a major part of which perished in 1945. The reconstruction as a socialist city deformed almost everything that was historical. This second trauma of deprivation, until this day, created and determines a culture of constructive controversy within the citizens´ initiatives of Dresden. The complexity, historicity as well as the extraction and synthesis of inter-disciplinary subject matters in the work at hand required the use of a qualitative paradigm, in particular the approach of Behavior Setting (BARKER, 1975) and the Qualitative Content Analysis (MAYRING, 1990). Based on the German tradition of communicating local developmental processes in the regional policy research and with the help of a literary exploration in the areas of environmental and decision making psychology, political science, and urban and transport ecology, this work displays the most fundamental facets and perspectives of controversial decisions in a municipal context.

Automatinė įrodymų sistema koreliatyvių žinių logikai yra pristatoma disertacijoje. Sistemą sudaro sekvencinis skaičiavimas GS-LCK ir įrodymo paieškos procedūra GS-LCK-PROC. Sekvencinis skaičiavimas yra pagrįstas, pilnas ir tenkina taisyklių apverčiamumo, silpninimo, prastinimo ir pjūvio leistinumo savybes. Procedūra GS-LCK-PROC yra baigtinė ir leidžia patikrinti, ar sekvencija yra išvedama. Taip pat buvo įrodytas koreliatyvių žinių logikos išsprendžiamumas. Naudojant baigtinę procedūra GS-LCK-PROC, visų koreliatyvių žinių logikos formulių tapatus teisingumas gali būti patikrintas. / Automated proof system for logic of correlated knowledge is presented in the dissertation. The system consists of the sequent calculus GS-LCK and the proof search procedure GS-LCK-PROC. Sequent calculus is sound, complete and satisfy the properties of invertibility of rules, admissibility of weakening, contraction and cut. The procedure GS-LCK-PROC is terminating and allows to check if the sequent is provable. Also decidability of logic of correlated knowledge has been proved. Using the terminating procedure GS-LCK-PROC the validity of all formulas of logic of correlated knowledge can be checked.