{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T09:08:24Z","timestamp":1725872904509},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662540688"},{"type":"electronic","value":"9783662540695"}],"license":[{"start":{"date-parts":[[2016,12,3]],"date-time":"2016-12-03T00:00:00Z","timestamp":1480723200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-662-54069-5_8","type":"book-chapter","created":{"date-parts":[[2016,12,2]],"date-time":"2016-12-02T08:43:15Z","timestamp":1480668195000},"page":"91-105","source":"Crossref","is-referenced-by-count":1,"title":["Random Models for Evaluating Efficient B\u00fcchi Universality Checking"],"prefix":"10.1007","author":[{"given":"Corey","family":"Fisher","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seth","family":"Fogarty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe","family":"Vardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,12,3]]},"reference":[{"issue":"3","key":"8_CR1","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/BF01470748","volume":"148","author":"JR B\u00fcchi","year":"1962","unstructured":"B\u00fcchi, J.R.: Turing-machines and the Entscheidungsproblem. Math. Ann. 148(3), 201\u2013213 (1962)","journal-title":"Math. Ann."},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Doyen, L., Raskin, J.: Antichains for the automata-based approach to model-checking. arXiv preprint arXiv:0902.3958 (2009)","DOI":"10.2168\/LMCS-5(1:5)2009"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Fisher, C., Fogarty, S., Vardi, M.: Random models for efficient B\u00fcchi universality checking. Technical report. Department of Computer Science, Rice University, Houston, TX, October 2016. http:\/\/www.cs.rice.edu\/~vardi","DOI":"10.1007\/978-3-662-54069-5_8"},{"key":"8_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-642-12002-2_17","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"S Fogarty","year":"2010","unstructured":"Fogarty, S., Vardi, M.Y.: Efficient B\u00fcchi Universality Checking. In: Esparza, J., Majumdar, R. (eds.) TACAS 2010. LNCS, vol. 6015, pp. 205\u2013220. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-12002-2_17"},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-642-00768-2_2","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"S Fogarty","year":"2009","unstructured":"Fogarty, S., Vardi, M.Y.: B\u00fcchi complementation and size-change termination. In: Kowalewski, S., Philippou, A. (eds.) TACAS 2009. LNCS, vol. 5505, pp. 16\u201330. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-00768-2_2"},{"issue":"395","key":"8_CR6","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1080\/01621459.1986.10478342","volume":"81","author":"O Frank","year":"1986","unstructured":"Frank, O., Strauss, D.: Markov graphs. J. Am. Stat. Assoc. 81(395), 832\u2013842 (1986)","journal-title":"J. Am. Stat. Assoc."},{"key":"8_CR7","doi-asserted-by":"publisher","unstructured":"Kleinberg, J., Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A.: The web as a graph: measurements, models, and methods. In: Asano, T., Imai, H., Lee, D.T., Nakano, S., Tokuyama, T. (eds.) COCOON 1999. LNCS, vol. 1627, pp. 1\u201317. Springer, Heidelberg (1999). doi: 10.1007\/3-540-48686-0_1","DOI":"10.1007\/3-540-48686-0_1"},{"issue":"1","key":"8_CR8","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1002\/rsa.3240010106","volume":"1","author":"RM Karp","year":"1990","unstructured":"Karp, R.M.: The transitive closure of a random digraph. Random Struct. Alg. 1(1), 73\u201393 (1990)","journal-title":"Random Struct. Alg."},{"issue":"3","key":"8_CR9","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1145\/377978.377993","volume":"2","author":"O Kupferman","year":"2001","unstructured":"Kupferman, O., Vardi, M.Y.: Weak alternating automata are not that weak. ACM Trans. Comput. Logic (TOCL) 2(3), 408\u2013429 (2001)","journal-title":"ACM Trans. Comput. Logic (TOCL)"},{"key":"8_CR10","unstructured":"Leslie, T.: Efficient approaches to subset construction. Technical report. University of Waterloo, Canada (1995)"},{"key":"8_CR11","doi-asserted-by":"publisher","unstructured":"de Wulf, M., Doyen, L., Henzinger, T.A., Raskin, J.-F.: Antichains: a new algorithm for checking universality of finite automata. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol. 4144, pp. 17\u201330. Springer, Heidelberg (2006). doi: 10.1007\/11817963_5","DOI":"10.1007\/11817963_5"},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/978-3-642-18098-9_28","volume-title":"Implementation and Application of Automata","author":"M-H Tsai","year":"2011","unstructured":"Tsai, M.-H., Fogarty, S., Vardi, M.Y., Tsay, Y.-K.: State of B\u00fcchi complementation. In: Domaratzki, M., Salomaa, K. (eds.) CIAA 2010. LNCS, vol. 6482, pp. 261\u2013271. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-18098-9_28"},{"key":"8_CR13","unstructured":"Michel, M.: Complementation is more difficult with automata on infinite words. CNET, Paris (1988). 15"},{"key":"8_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/978-3-642-23217-6_13","volume-title":"CONCUR 2011 \u2013 Concurrency Theory","author":"PA Abdulla","year":"2011","unstructured":"Abdulla, P.A., Chen, Y.-F., Clemente, L., Hol\u00edk, L., Hong, C.-D., Mayr, R., Vojnar, T.: Advanced ramsey-based B\u00fcchi automata inclusion testing. In: Katoen, J.-P., K\u00f6nig, B. (eds.) CONCUR 2011. LNCS, vol. 6901, pp. 187\u2013202. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-23217-6_13"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Safra, S.: On the complexity of $$\\omega $$ -automata. In: 29th Annual Symposium on Foundations of Computer Science, pp. 319\u2013327. IEEE (1988)","DOI":"10.1109\/SFCS.1988.21948"},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"Sistla, A.P., Vardi, M.Y., Wolper, P.: The complementation problem for B\u00fcchi automata with applications to temporal logic. Theor. Comput. Sci. 49(2), 217\u2013237 (1987)","DOI":"10.1016\/0304-3975(87)90008-9"},{"key":"8_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/11591191_28","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"D Tabakov","year":"2005","unstructured":"Tabakov, D., Vardi, M.Y.: Experimental evaluation of classical automata constructions. In: Sutcliffe, G., Voronkov, A. (eds.) LPAR 2005. LNCS, vol. 3835, pp. 396\u2013411. Springer, Heidelberg (2005). doi: 10.1007\/11591191_28"},{"key":"8_CR18","unstructured":"Tabakov, D., Vardi, M.Y.: Model checking B\u00fcchi specifications. In: Proceedings of 1st International Conference on Language and Automata Theory and Applications, pp. 565\u2013576 (2007)"},{"key":"8_CR19","unstructured":"Vardi, M., Wolper, P.: An automata-theoretic approach to automatic program verification. In: Proceedings of the First Symposium on Logic in Computer Science, pp. 322\u2013331. IEEE Computer Society (1986)"},{"key":"8_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/978-3-540-70918-3_2","volume-title":"STACS 2007","author":"MY Vardi","year":"2007","unstructured":"Vardi, M.Y.: The B\u00fcchi complementation saga. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 12\u201322. Springer, Heidelberg (2007). doi: 10.1007\/978-3-540-70918-3_2"},{"issue":"1","key":"8_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.1994.1092","volume":"115","author":"MY Vardi","year":"1994","unstructured":"Vardi, M.Y., Wolper, P.: Reasoning about infinite computations. Inf. Comput. 115(1), 1\u201337 (1994)","journal-title":"Inf. Comput."}],"container-title":["Lecture Notes in Computer Science","Logic and Its Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-54069-5_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,16]],"date-time":"2019-09-16T05:53:39Z","timestamp":1568613219000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-54069-5_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,3]]},"ISBN":["9783662540688","9783662540695"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-54069-5_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016,12,3]]}}}