@techreport{TR-IC-01-20,
  number = {IC-01-20},
  author = {Arnaldo V. Moura and Guilherme A. Pinto},
  title = {Classes of Timed Automata and the Undecidability of Universality},
  month = {December},
  year = {2001}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 16 pages.
    \par\selectlanguage{brazil}\textbf{Resumo}
      O problema da universalidade para Autômatos Temporizados (ATs)
      determinísticos é PSPACE-completo mas torna-se altamente
      indecidível quando não-determinismo irrestrito é permitido. Mais
      precisamente, o problema da universalidade para AT
      não-determinísticos é $\Pi_1^1$-difícil e ainda está em aberto
      se é $\Pi_1^1$-completo. É interessante notar que toda a
      hierarquia aritmética está contida neste salto de
      computabilidade entre determinismo e não-determinismo. Neste
      artigo, nós consideramos três tipos de restrição sintática para
      AT não-determinísticos, que podem contribuir para um melhor
      entendimento da dificuldade de se testar universalidade de TA.
      Para os dois primeiros tipos, que têm interesse independente, o
      problema da universalidade é $\Pi_1^1$-completo. Para o terceiro
      tipo, universalidade é $\Pi_1^0$-completo, o que é o mesmo que
      dizer que o problema complementar é completo para a classes dos
      problemas recursivamente enumeráveis. Nós também mostramos que
      todas as restrições definem subclasses próprias da classe de
      linguagens temporizadas definidas por AT não-determinísticos; e
      estabelecemos as relações entre todas as classes.
    
    \par\selectlanguage{english}\textbf{Abstract}
      Universality for deterministic Timed Automata (TA) is
      PSPACE-complete but becomes highly undecidable when unrestricted
      nondeterminism is allowed. More precisely, universality for
      nondeterministic TA is $\Pi_1^1$-hard and it is still open
      whether it is $\Pi_1^1$-complete. It is interesting to note that
      the entire arithmetical hierarchy is contained in this
      computability gap between determinism and nondeterminism. In
      this paper we consider three types of syntactical restrictions
      to nondeterministic TA, which may contribute to a better
      understanding of the universality problem for TA. For the first
      two types, which are of independent interest, the universality
      problem is shown to be $\Pi_1^1$-complete. For the third one,
      universality is $\Pi_1^0$-complete, which is the same as saying
      that the complementary problem is complete in the recursively
      enumerable class. We also show that all the restrictions define
      proper subclasses of the class of timed languages defined by
      nondeterministic TA; and establish the relationships between the
      classes.
  }
}