Paper: On simultaneously determinizing and complementing ω-automata (at LICS 1989)

Authors: E. Allen Emerson Charanjit S. Jutla

Abstract

The authors give a construction to determine and complement simultaneously a Buchi automaton in infinite strings, with an exponential blowup in states and a linear blowup in the number of pairs. An exponential lower bound is already known. The previous best construction was double exponential. The present result permits exponentially improved essentially optimal decision procedures for various modal logics of programs. It also gives exponentially improved conversions between various kinds of ω automata

BibTeX

  @InProceedings{EmersonJutla-Onsimultaneouslydet,
    author = 	 {E. Allen Emerson and Charanjit S. Jutla},
    title = 	 {On simultaneously determinizing and complementing ω-automata },
    booktitle =  {Proceedings of the Fourth Annual IEEE Symposium on Logic in Computer Science (LICS 1989)},
    year =	 {1989},
    month =	 {June}, 
    pages =      {333--342},
    location =   {Pacific Grove, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }