We study the decidability and complexity of verification problems for infinite-state systems. A fundamental question in formal verification is if the behaviour of one process is reproducible by another. This inclusion problem can be studied for various models of computation and behavioural preorders. It is generally intractable or even undecidable already for very limited computational models. The aim of this work is to clarify the status of the decidability and complexity of some well-known inclusion problems for suitably restricted computational models. In particular, we address the problems of checking strong and weak simulation and trace inclusion for processes definable by one-counter automata (OCA), that consist of a finite control and a single counter ranging over the non-negative integers. We take special interest of the subclass of one-counter nets (OCNs), that cannot fully test the counter for zero and which is subsumed both by pushdown automata and Petri nets / vector addition systems. Our new results include the PSPACE-completeness of strong and weak simulation, and the undecidability of trace inclusion for OCNs. Moreover, we consider semantic preorders between OCA/OCN and finite systems and close some gaps regarding their complexity. Finally, we study deterministic processes, for which simulation and trace inclusion coincide.

The principal focus of this thesis is the study of the real numbers regarded as a structure endowed with its usual addition and multiplication and the operations of raising to real powers. For our first main result we prove that any statement in the language of this structure is equivalent to an existential statement, and furthermore that this existential statement can be chosen independently of the concrete interpretations of the real power functions in the statement; i.e. one existential statement will work for any choice of real power functions. This result we call uniform model completeness. For the second main result we introduce the first order theory of raising to an infinite power, which can be seen as the theory of a class of real closed fields, each expanded by a power function with infinite exponent. We note that it follows from the first main theorem that this theory is model-complete, furthermore we prove that it is decidable if and only if the theory of the real field with the exponential function is decidable. For the final main theorem we consider the problem of expanding an arbitrary o-minimal expansion of a field by a non-trivial exponential function whilst preserving o-minimality. We show that this can be done under the assumption that the structure already defines exponentiation on a bounded interval, and a further assumption about the prime model of the structure.

A interpretação usual da obra de Rudolf Carnap, Der Logische Aufbau der Welt (Aufbau),assentada sobretudo na sua leitura por parte de Goodman e de Quine na década de 50, toma-o como um projeto empirista de explicitação dos nexos lógicos entre os conceitos de diferentes domínios teóricos e \"o dado\". Essa interpretação minimiza o problema epistemológico, central no Aufbau, da legitimação (da justificação, da validade de jure) das pretensões de conhecimento das ciências factuais (Realwissenschaften, em contraposição às Formalwissenschaften). Ao examinar o projeto de Carnap como um projeto neotranscendental de justificação do conhecimento empírico, inverte-se a prioridade concedida ao esclarecimento conceitual entre as motivações do Aufbau. Na concepção de epistemologia que subjaz a esta abordagem do Aufbau, Hume e Kant, empirismo e racionalismo aparecem como representações estilizadas e simplificadas da polarização que se exerceu sobre Carnap frente a um tópico proposto pela tradição filosófica: o conhecimento empírico, as leis universais das ciências factuais, são ou não são passíveis de justificação racional (e de que modo)? Tal inversão permite entender as teses e os passos da teoria da constituição de Carnap de maneira a dar conta de forma coerente e sistemática de aspectos dessa obra que a maioria das análises trata de modo fragmentado e desconectado. Sob essa luz, são abordado temas como a escolha do instrumental formal da teoria da constituição, o papel da teoria das descrições definidas e do modelo das definições implícitas, a tese da extensionalidade, o estruturalismo, o formalismo, as pressuposições extrasistemáticas, a relação da ordem epistêmica com a ordem lógica, a distinção entre \"o sistema\" (na forma ideal em que o concebe a teoria da constituição) e o \"esboço provisório\" que Carnap propõe no Aufbau a título de exemplo. Quatro problemas principais que comprometem seriamente esse projeto de Carnap são examinados contra o pano de fundo da leitura epistemológica proposta. Os dois primeiros (suposições extra-sistemáticas e construção do tempo e do espaço) dizem respeito ao \"esboço provisório\", mas são dificuldades que não se devem ao estado provisório dos próprios conceitos científicos mas à incapacidade desse esboço de ater-se aos preceitos da teoria da constituição de que pretende ser uma aplicação. As duas dificuldades restantes (finitismo e decidibilidade, e caráter inteiramente formal do sistema) afetam a própria concepção do sistema ideal. Como desiderata da teoria da constituição, terminam por se revelar incompatíveis com traços fundamentais do conhecimento empírico de cuja preservação não é possível abrir mão sem descaracterizá-lo profundamente. O caráter original do projeto carnapiano de justificação racional completa e cabal de todo o conhecimento empírico termina portanto por conduzi-lo a posições incompatíveis com o próprio empirismo. Para preservar \"o caráter aberto e a inevitável incerteza de todo conhecimento empírico, Carnap abrirá mão do sistema único e total de conceitos científicos como garantia da objetividade e da possibilidade de comunicação, substituindoo, depois do Aufbau, pelo princípio de tolerância ou da convencionalidade das formas de linguagem / The usual interpretation of the work of Rudolf Carnap, Der Logische Aufbau der Welt (Aufbau), rests on its reading by Goodman and Quine in the 50s, and takes it as an empiricist attempt to establish the logical connections between concepts of different theoretical domains and \"the given\". This interpretation minimizes the epistemological problem, central to the Aufbau, of the legitimation (justification, validity de jure) of the claims to knowledge of the factual sciences (Realwissenschaften, as opposed to Formalwissenschaften). By examining Carnap´s project as a project of neotranscendental justification of empirical knowledge, the priority given to conceptual clarification between the motivations of the Aufbau is reversed. In the conception of epistemology behind the new approach of the Aufbau, Hume and Kant, empiricism and rationalism appear as simplified and stylized representations of the polarization that is exerted on Carnap in his definition against a topic proposed by the philosophical tradition: the universal laws of empirical science are or are not capable of rational justification (and how)? This allows us to understand the arguments and the steps of Carnap\'s theory of constitution as coherent and systematic aspects of this work, often analysed in fragmented and disconnected ways. In this light, topics such as the choice of the formal instrumental of the theory of the constitution, the role of definite descriptions theory and of the use of implicit definitions, the thesis of extensionality, structuralism, formalism, extra- systematic assumptions, the relationship of epistemic and logic order, the distinction between \"the system\" (in the ideal way in which the theory of the constitution conceives it) and the \"tentative outline\" Carnap proposed in the Aufbau as an example are addressed. Four main problems which seriously undermine Carnap´s project are examined against the backdrop of the epistemological reading proposed. The first two (extrasystematic assumptions and construction of time and space) concern the \"tentative outline\", but they are not due to the provisional state of scientific concepts themselves but to the inability of this sketch to stick to the precepts of the theory of the constitution of which it aims to be an application. The two remaining difficulties (finitism and decidability, and the entirely formal character of the system) affect the conception of the ideal system. Being desiderata of the theory of the constitution, they will eventually prove incompatible with fundamental features of empirical knowledge of whose preservation one can not give up without deeply disfiguring it. The original character of the Carnapian project of a complete and full rational justification of all empirical knowledge thus ends by leading to a position incompatible with empiricism itself. To preserve the \"open character and the unavoidable uncertainty\" of all empirical knowledge, Carnap will then relinquish the unique and full system of scientific concepts as a guarantee of objectivity and of the possibility of communication, replacing it, after the Aufbau, by the principle of tolerance or conventionality of language forms

Les ontologies sont utilisées pour la représentation et l’interrogation de connaissances d’un domaine précis et peuvent être représentées en partie à l’aide des logiques de description légères. Ces ontologies peuvent être issues de plusieurs sources dont les données sont plus ou moins complétés, ainsi certaines données peuvent être incomplètes ou incohérentes empêchant la déduction d’autres données. L’Answer Set Programming (ASP) est un langage de programmation logique non-monotone à base de règles permettant de représenter des données incomplètes mais il ne permet pas de représenter les logiques de description légères. Les règles existentielles généralisent les logiques de description légères et forment aussi un langage de programmation logique mais ne permettant pas la définition d’exceptions. A partir d’une étude théorique d’ASP et des règles existentielles nous proposons de regrouper en un seul formalisme ces deux langages, nous définissons le formalisme des programmes non-monotones existentiels permettant de traiter un programme provenant d’une ontologie avec exceptions. Cette extension a pour but de généraliser à la fois ASP et les règles existentielles et d’utiliser la puissance des solveurs ASP pour raisonner sur des ontologies avec exceptions. Cette étude propose d’approfondir les travaux sur la décidabilité d’un programme avec l’extension aux programmes non-monotones existentiels. Nous proposons aussi d’améliorer les résultats lies à l’interrogation d’un programme ASP ainsi qu’une implémentation d’une extension du solveur ASPeRiX pour traiter les programmes non-monotones existentiels. / Ontologies are meant to represent or to queryknowledge from a precise domain and can berepresented, in part, by logic formalisms such thatdescription logics. These ontologies can be providedby several sources where knowledge is more or lesscomplete, hence some data can be incomplete orincoherent preventing the deduction of other data.Answer Set Programming (ASP) formalism is anon-monotonic logic programming language based onrules, often used in knowledge representation, whichhas the feature to represent incomplete data.However, it’s impossible to represent lite descriptionlogics in ASP, because of existential variables in rules.Existential rules generalize lite description logics andalso form a programmation logic language that butdoesn’t offer the possibility to represent exceptions.Based on a theoritical study of ASP and existentialrules, we propose to gather both languages in aunique formalism, we define non-monotonic existentialprogram allowing to deal with ontology withexceptions. This extension aims to generalize bothASP and existential rules program and to use theefficiency of ASP solvers to reason on ontologies withexceptions. This thesis propose to deepen worksabout entailment and decidability of a non-monotonicexistential program. Another result from this study isthe improvement of interrogation in ASP and theimplementation of an extension of the ASPeRiX solverto deal with non-monotonic existential programs.

A interpretação usual da obra de Rudolf Carnap, Der Logische Aufbau der Welt (Aufbau),assentada sobretudo na sua leitura por parte de Goodman e de Quine na década de 50, toma-o como um projeto empirista de explicitação dos nexos lógicos entre os conceitos de diferentes domínios teóricos e \"o dado\". Essa interpretação minimiza o problema epistemológico, central no Aufbau, da legitimação (da justificação, da validade de jure) das pretensões de conhecimento das ciências factuais (Realwissenschaften, em contraposição às Formalwissenschaften). Ao examinar o projeto de Carnap como um projeto neotranscendental de justificação do conhecimento empírico, inverte-se a prioridade concedida ao esclarecimento conceitual entre as motivações do Aufbau. Na concepção de epistemologia que subjaz a esta abordagem do Aufbau, Hume e Kant, empirismo e racionalismo aparecem como representações estilizadas e simplificadas da polarização que se exerceu sobre Carnap frente a um tópico proposto pela tradição filosófica: o conhecimento empírico, as leis universais das ciências factuais, são ou não são passíveis de justificação racional (e de que modo)? Tal inversão permite entender as teses e os passos da teoria da constituição de Carnap de maneira a dar conta de forma coerente e sistemática de aspectos dessa obra que a maioria das análises trata de modo fragmentado e desconectado. Sob essa luz, são abordado temas como a escolha do instrumental formal da teoria da constituição, o papel da teoria das descrições definidas e do modelo das definições implícitas, a tese da extensionalidade, o estruturalismo, o formalismo, as pressuposições extrasistemáticas, a relação da ordem epistêmica com a ordem lógica, a distinção entre \"o sistema\" (na forma ideal em que o concebe a teoria da constituição) e o \"esboço provisório\" que Carnap propõe no Aufbau a título de exemplo. Quatro problemas principais que comprometem seriamente esse projeto de Carnap são examinados contra o pano de fundo da leitura epistemológica proposta. Os dois primeiros (suposições extra-sistemáticas e construção do tempo e do espaço) dizem respeito ao \"esboço provisório\", mas são dificuldades que não se devem ao estado provisório dos próprios conceitos científicos mas à incapacidade desse esboço de ater-se aos preceitos da teoria da constituição de que pretende ser uma aplicação. As duas dificuldades restantes (finitismo e decidibilidade, e caráter inteiramente formal do sistema) afetam a própria concepção do sistema ideal. Como desiderata da teoria da constituição, terminam por se revelar incompatíveis com traços fundamentais do conhecimento empírico de cuja preservação não é possível abrir mão sem descaracterizá-lo profundamente. O caráter original do projeto carnapiano de justificação racional completa e cabal de todo o conhecimento empírico termina portanto por conduzi-lo a posições incompatíveis com o próprio empirismo. Para preservar \"o caráter aberto e a inevitável incerteza de todo conhecimento empírico, Carnap abrirá mão do sistema único e total de conceitos científicos como garantia da objetividade e da possibilidade de comunicação, substituindoo, depois do Aufbau, pelo princípio de tolerância ou da convencionalidade das formas de linguagem / The usual interpretation of the work of Rudolf Carnap, Der Logische Aufbau der Welt (Aufbau), rests on its reading by Goodman and Quine in the 50s, and takes it as an empiricist attempt to establish the logical connections between concepts of different theoretical domains and \"the given\". This interpretation minimizes the epistemological problem, central to the Aufbau, of the legitimation (justification, validity de jure) of the claims to knowledge of the factual sciences (Realwissenschaften, as opposed to Formalwissenschaften). By examining Carnap´s project as a project of neotranscendental justification of empirical knowledge, the priority given to conceptual clarification between the motivations of the Aufbau is reversed. In the conception of epistemology behind the new approach of the Aufbau, Hume and Kant, empiricism and rationalism appear as simplified and stylized representations of the polarization that is exerted on Carnap in his definition against a topic proposed by the philosophical tradition: the universal laws of empirical science are or are not capable of rational justification (and how)? This allows us to understand the arguments and the steps of Carnap\'s theory of constitution as coherent and systematic aspects of this work, often analysed in fragmented and disconnected ways. In this light, topics such as the choice of the formal instrumental of the theory of the constitution, the role of definite descriptions theory and of the use of implicit definitions, the thesis of extensionality, structuralism, formalism, extra- systematic assumptions, the relationship of epistemic and logic order, the distinction between \"the system\" (in the ideal way in which the theory of the constitution conceives it) and the \"tentative outline\" Carnap proposed in the Aufbau as an example are addressed. Four main problems which seriously undermine Carnap´s project are examined against the backdrop of the epistemological reading proposed. The first two (extrasystematic assumptions and construction of time and space) concern the \"tentative outline\", but they are not due to the provisional state of scientific concepts themselves but to the inability of this sketch to stick to the precepts of the theory of the constitution of which it aims to be an application. The two remaining difficulties (finitism and decidability, and the entirely formal character of the system) affect the conception of the ideal system. Being desiderata of the theory of the constitution, they will eventually prove incompatible with fundamental features of empirical knowledge of whose preservation one can not give up without deeply disfiguring it. The original character of the Carnapian project of a complete and full rational justification of all empirical knowledge thus ends by leading to a position incompatible with empiricism itself. To preserve the \"open character and the unavoidable uncertainty\" of all empirical knowledge, Carnap will then relinquish the unique and full system of scientific concepts as a guarantee of objectivity and of the possibility of communication, replacing it, after the Aufbau, by the principle of tolerance or conventionality of language forms

Abstract Due to increasing amount of concurrency, systems have become difficult to design and analyse. In this effort, formal verification, which means proving the correctness of a system, has turned out to be useful. Unfortunately, the application domain of the formal verification methods is often indefinite, tools are typically unavailable, and most of the techniques do not suit especially well for the verification of software systems. These are the questions addressed in the thesis. A typical approach to modelling systems and specifications is to consider them parameterised by the restrictions of the execution environment, which results in an (infinite) family of finite-state verification tasks. The thesis introduces a novel approach to the verification of such infinite specification-system families represented as labelled transition systems (LTSs). The key idea is to exploit the algebraic properties of the correctness relation. They allow the correctness of large system instances to be derived from that of smaller ones and, in the best case, an infinite family of finite-state verification tasks to be reduced to a finite one, which can then be solved using existing tools. The main contribution of the thesis is an algorithm that automates the reduction method. A specification and a system are given as parameterised LTSs and the allowed parameter values are encoded using first order logic. Parameters are sets and relations over these sets, which are typically used to denote, respectively, identities of replicated components and relationships between them. Because the number of parameters is not limited and they can be nested as well, one can express multiply parameterised systems with a parameterised substructure, which is an essential property from the viewpoint of modelling software systems. The algorithm terminates on all inputs, so its application domain is explicit in this sense. Other proposed parameterised verification methods do not have both these features. Moreover, some of the earlier results on the verification of parameterised systems are obtained as a special case of the results presented here. Finally, several natural and significant extensions to the formalism are considered, and it is shown that the problem becomes undecidable in each of the cases. Therefore, the algorithm cannot be significantly extended in any direction without simultaneously restricting some other aspect.

No description available.

京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第18041号 / 理博第3919号 / 新制||理||1566(附属図書館) / 30899 / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)准教授 西村 進, 教授 加藤 毅, 教授 長谷川 真人 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DGAM

Datalog ist die relationale Variante der logischen Programmierung und ist eine Standard-Abfragesprache in der Datenbankentheorie geworden. Die Programmkomplexität von Datalog im bisherigen Hauptanwendungsgebiet, auf endlichen Strukturen, ist bekanntermassen in EXPTIME. Wir untersuchen die Komplexität von Datalog auf unendlichen Strukturen, motiviert durch mögliche Anwendungen von Datalog auf unendlichen Strukturen (z.B. linearen Ordnungen) im zeitlichen und räumlichen Schliessen, aber auch durch das aufkommende Interesse an unendlichen Strukturen bei verwandten theoretischen Problemen, wie Constraint Satisfaction Problems (CSP): Im Gegensatz zu endlichen Strukturen können Datalog-Berechnungen auf unendlichen Strukturen unendlich lange dauern, was zur Unentscheidbarkeit von Datalog auf unendlichen Strukturen führen kann. Aber auch in den entscheidbaren Fällen kann die Komplexität von Datalog auf unendlichen Strukturen beliebig hoch sein. Im Hinblick auf dieses Ergebnis widmen wir uns dann unendlichen Strukturen mit der niedrigsten Komplexität von Datalog: Wir zeigen, dass Datalog auf linearen Ordnungen (auch dichte und diskrete, mit oder ohne Konstanten und sogar gefärbte) und Baumordnungen EXPTIME-vollständig ist. Für die Bestimmung der oberen Schranke werden Werkzeuge für Datalog auf Ordnungen eingeführt: Ordnungstypen, Abstandstypen und typdisjunkte Programme. Die Typkonzepte liefern eine endliche Beschreibung der unendlichen Programmergebnisse und könnten auch für praktische Anwendungen von Interesse sein. Wir erzeugen spezielle typdisjunkte Programme, die sich ohne Rekursion lösen lassen. Ein Transfer unserer Methoden auf CSPs zeigt, dass CSPs auf unendlichen Strukturen mit beliebig hoher Zeitkomplexität vorkommen, wie Datalog. / Datalog is the relational variant of logic programming and has become a standard query language in database theory. The (program) complexity of datalog in its main context so far, on finite databases, is well known to be in EXPTIME. We research the complexity of datalog on infinite databases, motivated by possible applications of datalog to infinite structures (e.g. linear orders) in temporal and spatial reasoning on one hand and the upcoming interest in infinite structures in problems related to datalog, like constraint satisfaction problems: Unlike datalog on finite databases, on infinite structures the computations may take infinitely long, leading to the undecidability of datalog on some infinite structures. But even in the decidable cases datalog on infinite structures may have arbitrarily high complexity, and because of this result, we research some structures with the lowest complexity of datalog on infinite structures: Datalog on linear orders (also dense or discrete, with and without constants, even colored) and tree orders has EXPTIME-complete complexity. To achieve the upper bound on these structures, we introduce a tool set specialized for datalog on orders: Order types, distance types and type disjoint programs. The type concept yields a finite representation of the infinite program results, which could also be of interest for practical applications. We create special type disjoint versions of the programs allowing to solve datalog without the recursion inherent in each datalog program. A transfer of our methods shows that constraint satisfaction problems on infinite structures occur with arbitrarily high time complexity, like datalog.

Apresentaremos uma classe de energias potenciais $\\Pi \\in C^{\\infty}(\\Omega,R)$ que são s-decidíveis e que admitem funções auxiliares de Cetaev da forma $\\langle abla j^s\\Pi(q),q angle$, $q\\in \\Omega \\subset R^n$ que são s-resistentes. / We will present a class of potential energies $\\Pi \\in C^{\\infty}(\\Omega,R)$ that are s-decidable and that admit auxiliary functions of Cetaev of the form $\\langle abla j^s\\Pi(q),q angle$, $q \\in \\Omega \\subset R^n$ which are s-resistant.