Es wird die Axiomatisierbarkeit einer Klasse von temporalen Prädikatenlogiken über verzweigenden Strukturen gezeigt. Entscheidbarkeitsresultate folgen für diverse Fragmente dieser Logiken. Anwendungen werden diskutiert.

Notre pratique morale ordinaire, l’éthique normative ainsi que l’éthique appliquée présupposent que nos questions morales sont décidables non arbitrairement. Autrement dit, ces activités présupposent qu’il existe des réponses non arbitraires à nos questions morales. Le présent travail de recherche vise à questionner ce présupposé en explorant les réponses des trois principales familles de théories métaéthiques, soient le réalisme moral, l’antiréalisme moral et le constructivisme métaéthique, à la question « Les questions morales sont-elles décidables de manière non arbitraire? ». Notre but n’est pas de déterminer quelle théorie métaéthique est la meilleure, mais plutôt d’évaluer la possibilité que les questions morales soient décidables non arbitrairement. Nous défendrons que le réalisme moral semble compatible avec la décidabilité des questions morales et qu’au contraire, l’antiréalisme ainsi que le constructivisme semblent plus difficilement compatibles avec la décidabilité morale. Nous défendrons également que l’indécidabilité des questions morales, un problème pratique engendré par ces cadres métaéthiques, implique une aporie bien gênante. Si a priori on admet que ces trois familles de théories métaéthiques sont équiprobables, on pourrait alors affirmer grossièrement que nous avons deux chances sur trois de faire face, en pratique, au problème de l’indécidabilité morale et donc à l’aporie qu’elle implique. Cela justifiera pour nous l’intérêt d’explorer la possibilité d’une solution à cette aporie. Nous proposerons donc l’hypothèse selon laquelle la pratique du questionnement moral de manière aporétique, considérée comme une activité non cognitive, implique une certaine manière d’être qui n’est pas arbitraire. / Our ordinary moral practice, normative ethics and applied ethics presuppose that our moral questions are decidable non-arbitrarily. In other words, these activities presuppose that there are nonarbitrary answers to our moral questions. This very research aims to question this presupposition by exploring the answers of the three main families of metaethical theories, namely moral realism, moral antirealism and metaethical constructivism, to the question "Are moral questions decidable non-arbitrarily?". Our goal is not to determine which metaethical theory is the best, but rather to assess the possibility that moral questions are decidable non-arbitrarily. We will defend that moral realism seems to be compatible with the decidability of moral questions and that, on the contrary, antirealism and constructivism seem less compatible with moral decidability. Also, we will argue that the undecidability of moral questions, a practical problem generated by these metaethical frameworks, would involve a troublesome aporia. If a priori we admit that these three families of metaethical theories are equiprobable, we could then roughly affirm that we have two out of three chances to face the problem of moral undecidability and therefore the aporia it implies. This will justify for us the interest of exploring the possibility of a solution to this aporia. We will therefore propose the hypothesis according to which the practice of moral questioning in an aporetic way, considered as a non-cognitive activity, implies a certain way of being that is not arbitrary.

Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la logique, l'algèbre et aux applications. Cette étude est présentée au travers de quatre articles de recherche. Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess des automates de Parikh et en définit des généralisations et restrictions. L'automate de Parikh est un point de départ de cette thèse; nous montrons que ce modèle de calcul est équivalent à l'automate contraint que nous définissons comme un automate qui n'accepte un mot que si le nombre de fois que chaque transition est empruntée répond à une contrainte arithmétique. Ce modèle est naturellement étendu à l'automate de Parikh affine qui effectue une opération affine sur un ensemble de registres lors du franchissement d'une transition. Nous étudions aussi l'automate de Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de fois que chaque lettre y apparaît répond à une contrainte arithmétique. Le deuxième article, Bounded Parikh Automata, étudie les langages bornés des automates de Parikh. Un langage est borné s'il existe des mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont importants dans des domaines applicatifs et présentent usuellement de bonnes propriétés théoriques. Nous montrons que dans le contexte des langages bornés, le déterminisme n'influence pas l'expressivité des automates de Parikh. Le troisième article, Unambiguous Constrained Automata, introduit les automates contraints non ambigus, c'est-à-dire pour lesquels il n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de meilleures propriétés de clôture que l'automate contraint déterministe. Le problème de déterminer si le langage d'un automate contraint non ambigu est régulier est montré décidable. Le quatrième article, Algebra and Complexity Meet Contrained Automata, présente une étude des représentations algébriques qu'admettent les automates contraints et les automates de Parikh affines. Nous déduisons de ces caractérisations des résultats d'expressivité et de complexité. Nous montrons aussi que certaines hypothèses classiques en complexité computationelle sont reliées à des résultats de séparation et de non clôture dans les automates de Parikh affines. La thèse est conclue par une ouverture à un possible approfondissement, au travers d'un certain nombre de problèmes ouverts. / This thesis presents a study from the theoretical computer science perspective of computing models combining finite automata and arithmetic constraints. We focus on decidability questions, expressiveness, and closure properties, while opening the study to complexity, logic, algebra, and applications. This thesis is presented through four research articles. The first article, Affine Parikh Automata, continues the study of Klaedtke and Ruess on Parikh automata and defines generalizations and restrictions of this model. The Parikh automaton is one of the starting points of this thesis. We show that this model of computation is equivalent to the constrained automaton that we define as an automaton which accepts a word only if the number of times each transition is taken satisfies a given arithmetic constraint. This model is naturally extended to affine Parikh automata, in which an affine transformation is applied to a set of registers on taking a transition. We also study the Parikh automaton on letters, that is, an automaton which accepts a word only if the number of times each letter appears in the word verifies an arithmetic constraint. The second article, Bounded Parikh Automata, focuses on the bounded languages of Parikh automata. A language is bounded if there are words w_1, w_2, ..., w_k such that every word in the language can be written as w_1...w_1w_2...w_2 ... w_k...w_k. These languages are important in applications and usually display good theoretical properties. We show that, over the bounded languages, determinism does not influence the expressiveness of Parikh automata. The third article, Unambiguous Constrained Automata, introduces the concept of unambiguity in constrained automata. An automaton is unambiguous if there is only one accepting path per word of its language. We show that the unambiguous constrained automaton is an appealing model of computation which combines a better expressiveness and better closure properties than the deterministic constrained automaton. We show that it is decidable whether the language of an unambiguous constrained automaton is regular. The fourth article, Algebra and Complexity Meet Constrained Automata, presents a study of algebraic representations of constrained automata and affine Parikh automata. We deduce expressiveness and complexity results from these characterizations. We also study how classical computational complexity hypotheses help in showing separations and nonclosure properties in affine Parikh automata. The thesis is concluded by a presentation of possible future avenues of research, through several open problems.

Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la logique, l'algèbre et aux applications. Cette étude est présentée au travers de quatre articles de recherche. Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess des automates de Parikh et en définit des généralisations et restrictions. L'automate de Parikh est un point de départ de cette thèse; nous montrons que ce modèle de calcul est équivalent à l'automate contraint que nous définissons comme un automate qui n'accepte un mot que si le nombre de fois que chaque transition est empruntée répond à une contrainte arithmétique. Ce modèle est naturellement étendu à l'automate de Parikh affine qui effectue une opération affine sur un ensemble de registres lors du franchissement d'une transition. Nous étudions aussi l'automate de Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de fois que chaque lettre y apparaît répond à une contrainte arithmétique. Le deuxième article, Bounded Parikh Automata, étudie les langages bornés des automates de Parikh. Un langage est borné s'il existe des mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont importants dans des domaines applicatifs et présentent usuellement de bonnes propriétés théoriques. Nous montrons que dans le contexte des langages bornés, le déterminisme n'influence pas l'expressivité des automates de Parikh. Le troisième article, Unambiguous Constrained Automata, introduit les automates contraints non ambigus, c'est-à-dire pour lesquels il n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de meilleures propriétés de clôture que l'automate contraint déterministe. Le problème de déterminer si le langage d'un automate contraint non ambigu est régulier est montré décidable. Le quatrième article, Algebra and Complexity Meet Contrained Automata, présente une étude des représentations algébriques qu'admettent les automates contraints et les automates de Parikh affines. Nous déduisons de ces caractérisations des résultats d'expressivité et de complexité. Nous montrons aussi que certaines hypothèses classiques en complexité computationelle sont reliées à des résultats de séparation et de non clôture dans les automates de Parikh affines. La thèse est conclue par une ouverture à un possible approfondissement, au travers d'un certain nombre de problèmes ouverts. / This thesis presents a study from the theoretical computer science perspective of computing models combining finite automata and arithmetic constraints. We focus on decidability questions, expressiveness, and closure properties, while opening the study to complexity, logic, algebra, and applications. This thesis is presented through four research articles. The first article, Affine Parikh Automata, continues the study of Klaedtke and Ruess on Parikh automata and defines generalizations and restrictions of this model. The Parikh automaton is one of the starting points of this thesis. We show that this model of computation is equivalent to the constrained automaton that we define as an automaton which accepts a word only if the number of times each transition is taken satisfies a given arithmetic constraint. This model is naturally extended to affine Parikh automata, in which an affine transformation is applied to a set of registers on taking a transition. We also study the Parikh automaton on letters, that is, an automaton which accepts a word only if the number of times each letter appears in the word verifies an arithmetic constraint. The second article, Bounded Parikh Automata, focuses on the bounded languages of Parikh automata. A language is bounded if there are words w_1, w_2, ..., w_k such that every word in the language can be written as w_1...w_1w_2...w_2 ... w_k...w_k. These languages are important in applications and usually display good theoretical properties. We show that, over the bounded languages, determinism does not influence the expressiveness of Parikh automata. The third article, Unambiguous Constrained Automata, introduces the concept of unambiguity in constrained automata. An automaton is unambiguous if there is only one accepting path per word of its language. We show that the unambiguous constrained automaton is an appealing model of computation which combines a better expressiveness and better closure properties than the deterministic constrained automaton. We show that it is decidable whether the language of an unambiguous constrained automaton is regular. The fourth article, Algebra and Complexity Meet Constrained Automata, presents a study of algebraic representations of constrained automata and affine Parikh automata. We deduce expressiveness and complexity results from these characterizations. We also study how classical computational complexity hypotheses help in showing separations and nonclosure properties in affine Parikh automata. The thesis is concluded by a presentation of possible future avenues of research, through several open problems.

Submitted by Sandra Maria Neri Santiago (sandra.neri@ufpe.br) on 2016-04-18T18:26:00Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) UFPe.FDR.Dissertação.UzielSantana..pdf: 3772684 bytes, checksum: 48d7f4655b26e4e7cd0a59cd4b7d3026 (MD5) / Made available in DSpace on 2016-04-18T18:26:00Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) UFPe.FDR.Dissertação.UzielSantana..pdf: 3772684 bytes, checksum: 48d7f4655b26e4e7cd0a59cd4b7d3026 (MD5) Previous issue date: 2005-09-29 / Este trabalho de pesquisa científica, de natureza dissertativa, tem como objeto de estudo uma construção terminológico-conceptual, por certo analítica e distintiva, dos institutos jurídico-processuais, Litígio e Lide, incluindo nesta perspectiva de investigação, apriorística e eminentemente, teorética, uma análise empírico-crítica do fenômeno da teleologicidade processual e da decidibilidade de conflitos, apontando-se e aplicando-se, a posteriori, as implicações teorético-conceptual-metodológicas e tecnológico-pragmáticas que tal distinção traz, como corolário, para a Ciência Jurídico-Processual – e suas instituições e institutos fundamentais – e para a resolução de questões aparentemente aporemáticas da teoria jurídico-processual. Para a consecução deste objeto/problema, fizemos, preliminarmente, uma análise teórico-conceptual e histórico-descritiva dos institutos Litígio e Lide a partir da leitura da dogmática jurídico-processual clássica e moderna, posto que, até então, tais institutos são tomados como elementos conceptuais de mesma referibilidade fenomênica e terminológica. Em seguida, para justificar e mostrar a razão de ser da distinção proposta, demonstramos que tal indiscernibilidade e imprecisão terminológicas resultam numa série de aporias conceptuais para a teoria do processo e, em assim sendo, assentimos, peremptoriamente, como um imperativo categórico e como um verdadeiro pressuposto das teses aqui assentidas, que não há que se falar em conhecimento científico, em Ciência Jurídico-Processual, caracterizada pelos atributos da neutralidade axiológica, da asseptabilidade método-epistemológica, da assertibilidade do discurso científico e da verdade científica, sem a construção de uma terminologia jurídico-conceptual, por certo, específica, apurada e precisa. Nesta perspectiva, assentimos que os termos Litígio e Lide são elementos conceptuais de bedeutung (referência) e sinn (sentido) diferentes, sendo o Litígio um pressuposto processual de natureza fáctico-causal-sociológica, de referibilidade extrínseca, portanto, exoprocessual, caracterizado pela contendere de sujeitos em face de uma pretensão – resistida ou insatisfeita – vetorialmente contrária ao interesse da outra parte e a Lide, por sua vez, um suposto processual – conditio sine qua non do processo – de natureza jurídico-processual stricto sensu, de referibilidade intrínseca, portanto, endoprocessual, caracterizada por uma relação jurídico-processual sinalagmática entre partes e o Estado-juiz. Em síntese, a Lide seria o resultado da dedução quantitativa e qualitativa em juízo do Litígio. Tal construção analítico-distintiva teria, assim, um alto grau de aplicabilidade, sobretudo, para se elucidar algumas aporias da teoria jurídico-processual, tais como a asserção do atributo da jurisdicionalidade na chamada jurisdição voluntária e na aplicação do conceito de Lide na processualística penal. Do mesmo modo, agora do ponto de vista da análise empírico-crítica consecutada, chegamos à conclusão de que a teleologicidade processual, a priori, é a decidibilidade da Lide e, tão-somente, a posteriori – sem isso constituir um telos necessário – a decidibilidade do Litígio; assim também, concluímos que as técnicas processuais de estruturação e formatação de procedimentos diferenciados (especiais) e de limitação da cognição do juiz (Lide < Litígio) são utilizadas, muitas vezes, com influências ideológicas que repercutem, assim, no âmbito de abrangência da res judicata, no direito de acesso à justiça e nos princípios da inafastabilidade do controle jurisdicional e da congruência. / This scientific research project, presented in the format of a dissertation, has as study object a terminological and conceptual construction, more correctly analytic and distinctive, of the institutes legal and procedural, Dispute and Lawsuit, including in this investigation perspective, aprioristic and eminently, theoretical, an empiric and critical analysis of the phenomenon of the teleologicity and the decidability, indicating itself and applying, a posteriori, implications theoretic, conceptual, methodological, technological and pragmatic that such distinction brings, as corollary, for the science legal procedural – and their institutions and fundamental institutes – and for the resolution of questions apparently of difficult solution (aporematicas) of the theory legal procedural. For the development of this problem we have, in the first time, a descriptive conceptual and historic theoretical analysis of institutes Dispute and Lawsuit from the dogmatist’s reading legal procedural classic and modern, in such way that, here such institutes are taken as the conceptual elements in the same way reference phenomenalist and terminological. To justify and show the existence of this proposition we demonstrate then, that such an indiscernibility and terminological imprecision resulting in a set of aporias (of difficult solution) conceptual for the theory of the process and, we approve this form, peremptorily, like a categorical imperative and like a presupposed truly of theses here approved, that cannot speak himself in scientific knowledge, in science legal procedural, characterized by attributes of neutrality axiological, of the acceptability method epistemological, of the assertibility of the scientific speech and scientific truth, without the development of a legal and conceptual terminology, more precisely, specific, refined and precise. In this perspective we approve that terms Dispute and Lawsuit are the conceptual elements of bedeutung (reference) and sinn (sense) different, being Dispute one presupposition procedural of artificial, causal, and sociological nature, of reference extrinsic, therefore, exoprocedural characterized by contendere of litigants in face of a pretension – resisted or unsatisfied – vectorially contrary to the interest of the other party and the Lawsuit, in turn, a presumption procedural – condition sine qua of the process – of natural legal procedural stricto sensu, intrinsic reference, therefore, characterized by a relation legal procedural synallagmatic between parts and the state judges. In synthesis Lawsuit would be the result of the quantitative and qualitative deduction in judgment of the Dispute. So such a distinctive analytic construction would have a high degree of applicability, especially, for the resolution of difficult solution questions (aporias) of the theory legal procedural, as the affirmation of the jurisdictional attribute in the voluntary jurisdiction and in the application of the concept of Lawsuit in the criminal process. Of the point of view of the critical empiric analyses achieved we arrive now to the conclusion in a similar way of which teleologicity procedural, a priori, is the decidability of Lawsuit and, only, a posteriori – without this to constitute a necessary telos – the decidability of the Dispute; thus also, we conclude that the technical procedurals of structuring and formatting of procedures differentiated (special) and of limitation of the judge’s knowledge (Lawsuit<Dispute) are used, several times, with the ideological influences that reverberate, so, in the context of the res judicata, in the law of access to the justice and in principles of the jurisdictional control and of the congruence.