Grau de indecidibilidade da universidade para subclasses de automatos temporizados

Autômatos Temporizados são uma generalização de w-Autômatos, e de Autômatos Finitos por conseqüência, interpretados sobre palavras infinitas temporizadas, onde a cada símbolo está associado um tempo de ocorrência. O problema da universalidade, dizer se um dado autômato aceita todas as palavras, é PSPACE-completo para autômatos determinísticos; mas é altamente indecidível quando não-determinismo irrestrito é permitido. Mais precisamente, universalidade para autômatos temporizados não-determinísticos é Til-difícil e o exato grau de indecidibilidade do problema ainda está em aberto na literatura. Nesta tese definimos três sub classes de autômatos temporizados não-determinísticos, modificando a sintaxe dos autômatos, de modo a impor restrições ao não-determinismo e permitir a determinação do exato grau de indecidibilidade para universalidade. Para as duas primeiras classes, que são de interesse independente, mostramos que o problema da universalidade é π1 completo. Para a terceira, é π° completo. Também estabelecemos os relacionamentos de expressividade entre as classes e mostramos que todas são subclasses próprias de autômatos temporizados não-determinísticos. Estes resultados mostram que qualquer que seja o grau de indecidibilidade do problema em aberto na literatura, ele será surpreendente do ponto de vista da expressividade das classes.Timed Auto mata are a generalization of w-Automata, and of Finite Automata as a consequence, interpreted over infinite timed words, where each symbol is associated to an occurrence time. The universality problem, whether a given automaton accepts every word, is PSPACE-complete for deterministic automata; but becomes highly undecidable when unrestricted nondeterminism is allowed. More precisely, universality for nondeterministic timed automata is IJl-hard and the exact degree of undecidability is still open in the literature. In this thesis we define three subclasses of nondeterministic timed automata, modifying the syntax of the automata, in order to impose restrictions on the nondeterminism and allow the determination of the exact degree of undecidability for universality. For the first two, which are of independent interest, we show that the universality problem is π1 complete. For the third one, universality is π° complete. We also establish the relationships between these classes; and show that ali three are proper subclasses of nondeterministic timed automata. These results show that whatever the degree of undecidability of the open problem may be, it will be surprising from the point of view of the expressiveness of the classes