Logic in Computer Science (LICS 1989)

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

Authors: Emerson, E.A. Jutla, C.S.

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 = 	 {Emerson, E.A. and Jutla, C.S.},
    title = 	 {On simultaneously determinizing and complementing ω-automata },
    booktitle =  {Proceedings of the Fourth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1989},
    year =	 1989,
    editor =	 {Rohit Parikh},
    month =	 {June}, 
    pages =      {333--342},
    location =   {Pacific Grove, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }