Abstract
In this paper we relate expressiveness of ω-automata to their complexity. Expressiveness is related to the different subclasses of the ω-regular languages that are accepted by automata that arise by restrictions on the acceptance conditions used. For example, different subclasses of the ω-regular languages arise from identifying the ω-languages with different classes and levels in the Borel hierarchy. Within the class of ω-regular languages, Wagner and Kaminski identified a strict hierarchy of languages induced by restricting the number of pairs allowed in a deterministic Rabin automaton (DRA).
Complexity relates to the smallest size automaton required to realize an ω-regular language. Safra shows that there are ω-regular languages for which deterministic Streett automata (DSA) are exponentially smaller than nondeterministic Buchi automata; in contrast, we show that for every DSA or DRA whose language is in class G δ , there exists a DBA of size linear in the original automaton. We show in particular that the language of a DRA is in class G δ if and only if the language can be realized as a DBA on the same transition structure as the DRA. We present a simple construction to transform a DRA with h pairs and n states to an equivalent DRA with O(n.h k) states and k pairs (i.e. DR(n,h)→ DR(n.h k, k)), where k is the Rabin Index (RI) of the language-the minimum number of pairs required to realize the language as a DRA. We also present a construction to translate a DSA into a minimum-pair DRA, achieving a transformation DS(n,h)→DR(n.h k, r), where k is the Streett index (SI), and r the RI of the language.
We prove that it is NP-hard to determine the RI (SI) of a language specified by a DRA (DSA). However, for a DRA (DSA) with h pairs, determining whether the RI (SI) is h, or any constant c, is in polynomial time.
supported by California MICRO program grant 93-026, DEC, and Intel
supported by NSF grant ECS 9111907 and California PATH program
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
O. Carton. Chain Automata. In IFIP 13th World Computer Congress, pages 451–458, August 1994.
E. S. Chang, Z. Manna, and A. Pnueli. The Safety-Progress Classification. In F. L. Bauer, W. Bauer, and H. Schwichtenberg, editors, Logic and Algebra of Specification, pages 143–202, 1993.
E. A. Emerson and C. L. Lei. Modalities for Model Checking: Branching Time Logic Strikes Back. Science of Computer Programming, 8(3):275–306, June 1987.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979.
M. Kaminski. A Classification of ω-regular languages. Theoretical Computer Science, 36:217–229, 1985.
S. C. Krishnan, A. Puri, and R. K. Brayton. Deterministic ω-automata vis-a-vis Deterministic Buchi Automata. In Algorithms and Computation, volume 834 of LNCS, pages 378–386. Springer-Verlag, 1994.
R. P. Kurshan. Automata-Theoretic Verification of Coordinating Processes. Princeton University Press, 1994. To appear.
Z. Manna and A. Pnueli. The Temporal Logic of Reactive and Concurrent Systems. Springer Verlag, 1992.
Kenneth L. McMillan. Personal communication, August 1994.
Shmuel Safra. Complexity of Automata on Infinite Objects. PhD thesis, The Weizmann Institute of Science, Rehovot, Israel, March 1989.
L. Staiger. Research in the theory of ω-languages. Journal of Information Processing and Cybernetics, 23:415–439, 1987.
W. Thomas. Automata on Infinite Objects. In J. van Leeuwen, editor, Formal Models and Semantics, volume B of Handbook of Theoretical Computer Science, pages 133–191. Elsevier Science, 1990.
K. Wagner. On ω-Regular Sets. Information and Control, 43:123–177, 1979.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Krishnan, S.C., Puri, A., Brayton, R.K. (1995). Structural complexity of ω-automata. In: Mayr, E.W., Puech, C. (eds) STACS 95. STACS 1995. Lecture Notes in Computer Science, vol 900. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-59042-0_69
Download citation
DOI: https://doi.org/10.1007/3-540-59042-0_69
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-59042-2
Online ISBN: 978-3-540-49175-0
eBook Packages: Springer Book Archive