文章基本信息
- 标题：Lower Bounds for Complementation of ω-Automata Via the Full Automata Technique
- 本地全文：下载
- 作者：Qiqi Yan
- 期刊名称：Logical Methods in Computer Science
- 印刷版ISSN：1860-5974
- 电子版ISSN：1860-5974
- 出版年度：2008
- 卷号：4
- 期号：01
- DOI：10.2168/LMCS-4(1:5)2008
- 出版社：Technical University of Braunschweig
- 摘要：
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 ω-automata, and prove an
optimal (Ω(nk))n lower bound for the complementation of
generalized Büchi automata, which holds for Streett automata as
well. - 关键词：Automata Techniques
