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

lmcs:992 - Logical Methods in Computer Science, March 19, 2008, Volume 4, Issue 1
Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique

Authors: Yan, Qiqi

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 \omega-automata, and obtain several lower bound results. Particularly, we prove an \omega((0.76n)^n) lower bound for B\"uchi complementation, which also holds for almost every complementation or determinization transformation of nondeterministic omega-automata, and prove an optimal (\omega(nk))^n lower bound for the complementation of generalized B\"uchi automata, which holds for Streett automata as well.


Source : oai:arXiv.org:0802.1226
DOI : 10.2168/LMCS-4(1:5)2008
Volume: Volume 4, Issue 1
Published on: March 19, 2008
Submitted on: July 25, 2007
Keywords: Computer Science - Logic in Computer Science,F.4.1,F.4.3


Share

Consultation statistics

This page has been seen 51 times.
This article's PDF has been downloaded 33 times.