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

Qiqi Yan

doi:10.2168/LMCS-4(1:5)2008

Qiqi Yan - 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 - https://doi.org/10.2168/LMCS-4(1:5)2008

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

Authors: Qiqi Yan

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üchi 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üchi automata, which holds for Streett automata as well.

https://doi.org/10.2168/LMCS-4(1:5)2008

Source: arXiv.org:0802.1226

Volume: Volume 4, Issue 1

Published on: March 19, 2008

Imported on: July 25, 2007

Keywords: Computer Science - Logic in Computer Science,F.4.1,F.4.3

Licence: arXiv.org - Non-exclusive license to distribute

Bibliographic References

21 Documents citing this article

Vojtěch Havlena;Ondřej Lengál;Yong Li;Barbora Šmahlíková;Andrea Turrini, Lecture notes in computer science, Modular Mix-and-Match Complementation of Büchi Automata, pp. 249-270, 2023, 10.1007/978-3-031-30823-9_13, https://doi.org/10.1007/978-3-031-30823-9_13.

Moshe Y. Vardi;Seth Fogarty;Yong Li;Yih-Kuen Tsay, Lecture notes in computer science, Towards a Grand Unification of Büchi Complementation Constructions, pp. 185-207, 2022, 10.1007/978-3-031-22337-2_9.

Yong Li;Andrea Turrini;Weizhi Feng;Moshe Y. Vardi;Lijun Zhang, Lecture notes in computer science, Divide-and-Conquer Determinization of Büchi Automata Based on SCC Decomposition, pp. 152-173, 2022, 10.1007/978-3-031-13188-2_8, https://doi.org/10.1007/978-3-031-13188-2_8.

Yong Li;Andrea Turrini;Xuechao Sun;Lijun Zhang, arXiv (Cornell University), Proving Non-inclusion of Büchi Automata Based on Monte Carlo Sampling, pp. 467-483, 2020, 10.1007/978-3-030-59152-6_26, https://arxiv.org/abs/2007.02282.

Yong Li;Moshe Y. Vardi;Lijun Zhang, 2020, On the Power of Unambiguity in Büchi Complementation, arXiv (Cornell University), 326, pp. 182-198, 10.4204/eptcs.326.12.

Yong Li;Andrea Turrini;Yu-Fang Chen;Lijun Zhang, Lecture notes in computer science, Learning Büchi Automata and Its Applications, pp. 38-98, 2019, 10.1007/978-3-030-17601-3_2.

Yong Li;Xuechao Sun;Andrea Turrini;Yu-Fang Chen;Junnan Xu, Lecture notes in computer science, ROLL 1.0: $$\omega $$ -Regular Language Learning Library, pp. 365-371, 2019, 10.1007/978-3-030-17462-0_23, https://doi.org/10.1007/978-3-030-17462-0_23.

Alexander Rabinovich, Lecture notes in computer science, Complementation of Finitely Ambiguous Büchi Automata, pp. 541-552, 2018, 10.1007/978-3-319-98654-8_44.

Joel D. Allred;Ulrich Ultes-Nitsche, Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, A Simple and Optimal Complementation Algorithm for Büchi Automata, 2018, Oxford United Kingdom, 10.1145/3209108.3209138.

Lukas Fleischer;Manfred Kufleitner, 2018, The complexity of weakly recognizing morphisms, RAIRO - Theoretical Informatics and Applications, 53, 1-2, pp. 1-17, 10.1051/ita/2018006.

Yong Li;Andrea Turrini;Lijun Zhang;Sven Schewe, Lecture notes in computer science, Learning to Complement Büchi Automata, pp. 313-335, 2017, 10.1007/978-3-319-73721-8_15.

František Blahoudek;Matthias Heizmann;Sven Schewe;Jan Strejček;Ming-Hsien Tsai, Lecture notes in computer science, Complementing Semi-deterministic Büchi Automata, pp. 770-787, 2016, 10.1007/978-3-662-49674-9_49.

Lukas Fleischer;Manfred Kufleitner, Loughborough University Research Repository (Loughborough University), Operations on Weakly Recognizing Morphisms, pp. 126-137, 2016, 10.1007/978-3-319-41114-9_10, https://figshare.com/articles/Operations_on_weakly_recognizing_morphisms/9405800.

Sven Schewe;Thomas Varghese, arXiv (Cornell University), Determinising Parity Automata, pp. 486-498, 2014, 10.1007/978-3-662-44522-8_41, https://arxiv.org/abs/1401.5394.

Sven Schewe;Thomas Varghese, arXiv (Cornell University), Tight Bounds for Complementing Parity Automata, pp. 499-510, 2014, 10.1007/978-3-662-44522-8_42, https://arxiv.org/abs/1406.1090.

Rui Wang;Wanwei Liu;Tun Li;Xiaoguang Mao;Ji Wang, 2013, Bounded Model Checking of ETL Cooperating with Finite and Looping Automata Connectives, Journal of Applied Mathematics, 2013, pp. 1-12, 10.1155/2013/462532, https://doi.org/10.1155/2013/462532.

Stefan Breuers;Christof Löding;Jörg Olschewski, Lecture notes in computer science, Improved Ramsey-Based Büchi Complementation, pp. 150-164, 2012, 10.1007/978-3-642-28729-9_10, https://doi.org/10.1007/978-3-642-28729-9_10.

Sven Schewe;Thomas Varghese, Lecture notes in computer science, Tight Bounds for the Determinisation and Complementation of Generalised Büchi Automata, pp. 42-56, 2012, 10.1007/978-3-642-33386-6_5.

Hrishikesh Karmarkar;Supratik Chakraborty, Lecture notes in computer science, On Minimal Odd Rankings for Büchi Complementation, pp. 228-243, 2009, 10.1007/978-3-642-04761-9_18.

Sven Schewe, Lecture notes in computer science, Tighter Bounds for the Determinisation of Büchi Automata, pp. 167-181, 2009, 10.1007/978-3-642-00596-1_13, https://doi.org/10.1007/978-3-642-00596-1_13.

Thomas Colcombet;Konrad Zdanowski, Lecture notes in computer science, A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata, pp. 151-162, 2009, 10.1007/978-3-642-02930-1_13.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 1534 times.

This article's PDF has been downloaded 330 times.