some image logo

HOME

SEARCH

CURRENT ISSUE

REGULAR ISSUES

   Volume 1 (2005)

   Volume 2 (2006)

   Volume 3 (2007)

   Volume 4 (2008)

      Issue 1

      Issue 2

      Issue 3

      Issue 4

   Volume 5 (2009)

   Volume 6 (2010)

   Volume 7 (2011)

   Volume 8 (2012)

   Volume 9 (2013)

   Volume 10 (2014)

   Volume 11 (2015)

   Volume 12 (2016)

   Volume 13 (2017)

SPECIAL ISSUES

SURVEY ARTICLES

AUTHORS

ABOUT

SERVICE

LOGIN

FAQ

SUPPORT

CONTACT

VOLUME 4, ISSUE 1, PAPER 5


Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique

©Qiqi Yan, Department of Computer Science and Engineering, Shanghai Jiao Tong University

Abstract
In this paper, we first introduce a lower bound technique for the state complexity of transformations of automata. Namely we suggest first considering the class of full automata in lower bound analysis, and later reducing the size of the large alphabet via alphabet substitutions. Then we apply such technique to the complementation of nondeterministic ω-automata, and obtain several lower bound results. Particularly, we prove an Ω((0.76n)n) lower bound for Büchi complementation, which also holds for almost every complementation or determinization transformation of nondeterministic omega-automata, and prove an optimal (Ω(nk))n lower bound for the complementation of generalized Büchi automata, which holds for Streett automata as well.

Publication date: March 19, 2008

Full Text: PDF | PostScript
DOI: 10.2168/LMCS-4(1:5)2008

Hit Counts: 8896

Creative Commons