Stuttgart, Univ., Studienarb., 2003.

Made available in DSpace on 2014-06-12T15:48:52Z (GMT). No. of bitstreams: 1 license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Nesta tese desenvolvemos uma caracterização das funções computáveis em espaço polinomial por meio da lógica de primeira ordem de seqüência binárias. Provamos, também, um resultado análogo ao Teorema de Parikh sobre limitação polinomial no tamanho de crescimento das funções de…níveis em tal sistema. Este trabalho é uma extensão natural do sistema desenvolvido pelo Professor Fernando Ferreira da Universidade de Lisboa, que trata das funções computáveis em tempo polinomial

ALCNIR+—ALCN augmented with transitive and inverse roles—is an expressive Description Logic which is especially well-suited for the representation of complex, aggregated objects. Despite its expressiveness, it has been conjectured that concept satisfiability for this logic could be decided in a comparatively efficient way. In this paper we prove the correctness of this conjecture by presenting a PSPACE algorithm for deciding satisfiability and subsumption of ALCNIR+-concepts. The space-efficiency of this tableau-based algorithm is due to a sophisticated guidance of the search for a solution. Moreover, this space-efficiency is not paid for with time-consumption; on the contrary, the guidance technique leads to very early refutation. This algorithm will be the basis for an efficient implementation.

Unification modulo the theory of Boolean algebras has been investigated by several autors. Nevertheless, the exact complexity of the decision problem for unification with constants and general unification was not known. In this research note, we show that the decision problem is complete for unification with constants and PSPACE-complete for general unification. In contrast, the decision problem for elementary unification (where the terms to be unified contain only symbols of the signature of Boolean algebras) is 'only' NP-complete.

In Description Logics (DLs), both tableau-based and automatabased algorithms are frequently used to show decidability and complexity results for basic inference problems such as satisfiability of concepts. Whereas tableau-based algorithms usually yield worst-case optimal algorithms in the case of PSpace-complete logics, it is often very hard to design optimal tableau-based algorithms for ExpTime-complete DLs. In contrast, the automata-based approach is usually well-suited to prove ExpTime upper-bounds, but its direct application will usually also yield an ExpTime-algorithm for a PSpace-complete logic since the (tree) automaton constructed for a given concept is usually exponentially large. In the present paper, we formulate conditions under which an on-the-fly construction of such an exponentially large automaton can be used to obtain a PSpace-algorithm. We illustrate the usefulness of this approach by proving a new PSpace upper-bound for satisfiability of concepts w.r.t. acyclic terminologies in the DL SI, which extends the basic DL ALC with transitive and inverse roles.

Unification of concept descriptions was introduced by Baader and Narendran as a tool for detecting redundancies in knowledge bases. It was shown that unification in the small description logic FL₀, which allows for conjunction, value restriction, and the top concept only, is already ExpTime-complete. The present paper shows that the complexity does not increase if one additionally allows for composition, union, and transitive closure of roles. It also shows that matching (which is polynomial in FL₀) is PSpace-complete in the extended description logic. These results are proved via a reduction to linear equations over regular languages, which are then solved using automata. The obtained results are also of interest in formal language theory. / An abridged version will appear in Proc. LPAR'01.

The game of Hex is of interest to the mathematics, algorithms, and artificial intelligence communities. It is a classical PSPACE-complete problem, and its invention is intrinsically tied to the Four Colour Theorem and the well-known strategy-stealing argument. Nash, Shannon, Tarjan, and Berge are among the mathematicians who have researched and published about this game. In this thesis we expand on previous research, further developing the mathematical theory and algorithmic techniques relating to Hex. In particular, we identify new classes of moves that can be pruned from consideration, and devise new algorithms to identify connection strategies efficiently. As a result of these theoretical improvements, we produce an automated solver capable of solving all 8 x 8 Hex openings and most 9 x 9 Hex openings; this marks the first time that computers have solved all Hex openings solved by humans. We also produce the two strongest automated Hex players in the world --- Wolve and MoHex --- and obtain both the gold and silver medals in the 2008 and 2009 International Computer Olympiads.

No description available.

Cette thèse s’inscrit dans le cadre de la programmation par contraintes quantifiées, un formalisme étendantla programmation par contraintes classique en ajoutant aux variables des quantificateurs existentiels ouuniversels, ce qui apporte en théorie une expressivité suffisante pour modéliser des problèmes avec adversaireou incertitude sur certains paramètres sous forme de problèmes appelés QCSP (Quantified Constraintsatisfaction Problem).Nous commençons par apporter une réponse aux difficultés de modélisation de problèmes réels dont estfrappée la programmation par contraintes quantifiées en introduisant une extension aux QCSP permettantd’expliciter les actions possibles de l’agent principal et de son adversaire. Puis, nous décrivons différentproblèmes grâce à ce formalisme, et discutons de la place de cette extension parmi les formalismes voisins créésen réponse à cette même difficulté de modélisation. Enfin, nous nous intéressons à la notion d’optimisationdans le cas des contraintes quantifiées, et apportons un formalisme d’optimisation de contraintes quantifiéespermettant d’exprimer des problèmes multi-niveaux non linéaires. / This thesis presents works in the research area of quantified constraint programming, which extends theconstraint programming framework by setting (existential and universal) quantifiers to the problem’s variables.This framework is theoretically expressive enough to model problems where an opponent or uncertainparameters are involved, under the form of Quantified Constraint Safisfaction Problems (QCSP).QCSPs suffer from a modeling difficulty that we solve by presenting an extension to this framework, in whichpossible moves for the principal agent and its opponent may be explicitely declared. Then, we describe realproblems using this extention, and discuss of its pros and cons against neighbour framework thar were createdto solve the same difficulty. Finally, we focus on quantifies optimization problems, and present a quantifiedoptimization framework thet allows the modeling of nonlinear multi-level problems.

Often the addition of metric operators to qualitative temporal logics leads to an increase of the complexity of satisfiability by at least one exponential. In this paper, we exhibit a number of metric extensions of qualitative temporal logics of the real line that do not lead to an increase in computational complexity. The main result states that the language obtained by extending since/until logic of the real line with the operators 'sometime within n time units', n coded in binary, is PSpace-complete even without the finite variability assumption. Without qualitative temporal operators the complexity of this language turns out to depend on whether binary or unary coding of parameters is assumed: it is still PSpace-hard under binary coding but in NP under unary coding.