{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:13:50Z","timestamp":1762100030403,"version":"3.30.2"},"reference-count":27,"publisher":"Duke University Press","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Notre Dame J. Formal Logic"],"published-print":{"date-parts":[[1996,4,1]]},"DOI":"10.1305\/ndjfl\/1040046086","type":"journal-article","created":{"date-parts":[[2003,2,25]],"date-time":"2003-02-25T21:10:08Z","timestamp":1046207408000},"source":"Crossref","is-referenced-by-count":40,"title":["The Price of Universality"],"prefix":"10.1215","volume":"37","author":[{"given":"Edith","family":"Hemaspaandra","sequence":"first","affiliation":[]}],"member":"73","reference":[{"key":"1","unstructured":"Balc\u00e1zar, J., J. D\u00edaz, and J. Gabarr\u00f3, <i>Structural Complexity I<\/i>, EATCS Monographs on Theoretical Computer Science vol. 11, Springer-Verlag, Berlin, 1995. Zbl 0638.68040 MR 91f:68058"},{"key":"2","doi-asserted-by":"crossref","unstructured":"Ben-Ari, M., J. Halpern, and A. Pnueli, \u201cDeterministic propositional dynamic logic: finite models, complexity and completeness,\u201d <i>Journal of Computer and System Sciences<\/i>, vol. 25 (1982), pp. 402\u2013417. Zbl 0512.03013 MR 84c:03033","DOI":"10.1016\/0022-0000(82)90018-6"},{"key":"3","doi-asserted-by":"crossref","unstructured":"Berger, R., \u201cThe undecidability of the dominoe problem,\u201d <i>Memoirs of the American Mathematical Society<\/i>, vol. 66 (1966). MR 36:49","DOI":"10.1090\/memo\/0066"},{"key":"4","doi-asserted-by":"crossref","unstructured":"Blackburn, P., and E. Spaan, \u201cA modal perspective on the computational complexity of attribute value grammar,\u201d <i>Journal of Logic, Language and Information<\/i>, vol. 2 (1993), pp. 129\u2013169. Zbl 0793.03018 MR 95f:03040","DOI":"10.1007\/BF01050635"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Emerson, E., and J. Halpern, \u201cDecision procedures and expressiveness in the temporal logic of branching time,\u201d <i>Journal of Computer and System Sciences<\/i>, vol. 30 (1985), pp. 194\u2013211. Zbl 0559.68051 MR 86j:68080","DOI":"10.1016\/0022-0000(85)90001-7"},{"key":"6","unstructured":"Fine, K., and R. Schurz, \u201cTransfer theorems for multimodal logics,\u201d <i>Proceedings Arthur Prior Memorial Conference<\/i>, Christchurch, New Zealand, 1989. Zbl 0919.03015 MR 98f:03016"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Fischer, M., and R. Ladner, \u201cPropositional dynamic logic of regular programs,\u201d <i>Journal of Computer and System Sciences<\/i>, vol. 18 (1979), pp. 194\u2013211. Zbl 0408.03014 MR 80f:68013","DOI":"10.1016\/0022-0000(79)90046-1"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Goranko, V., and S. Passy, \u201cUsing the universal modality: gains and questions,\u201d <i>Journal of Logic and Computation<\/i>, vol. 2 (1992), pp. 5\u201330. Zbl 0774.03003 MR 93h:03016","DOI":"10.1093\/logcom\/2.1.5"},{"key":"9","doi-asserted-by":"crossref","unstructured":"Halpern, J., and M. Moses, \u201cA guide to completeness and complexity for modal logics of knowledge and belief,\u201d <i>Artificial Intelligence<\/i>, vol. 54 (1992), pp. 319\u2013379. Zbl 0762.68029 MR 93c:03019","DOI":"10.1016\/0004-3702(92)90049-4"},{"key":"10","doi-asserted-by":"crossref","unstructured":"Halpern, J., and M. Vardi, \u201cThe complexity of reasoning about knowledge and time, I: Lower Bounds,\u201d <i>Journal of Computer and System Sciences<\/i>, vol. 38 (1989), pp. 195\u2013237. Zbl 0672.03015 MR 91f:68146","DOI":"10.1016\/0022-0000(89)90039-1"},{"key":"11","doi-asserted-by":"crossref","unstructured":"Harel, D., \u201cRecurring dominoes: making the highly undecidable highly understandable,\u201d pp. 177\u2013194 in <i>Proceedings of the Conference on Foundations of Computing Theory<\/i>, Springer Lecture Notes in Computer Science 158, Springer-Verlag, Berlin, 1983. Zbl 0531.68002 MR 734719","DOI":"10.1007\/3-540-12689-9_103"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Harel, D., \u201cEffective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness,\u201d <i>Journal of the ACM<\/i>, vol. 33 (1986), pp. 224\u2013248. MR 88a:68075","DOI":"10.1145\/4904.4993"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Harel, D., A. Pnueli, and J. Stavi, \u201cPropositional dynamic logic of nonregular programs,\u201d <i>Journal of Computer and System Sciences<\/i>, vol. 26 (1983), pp. 222\u2013243. Zbl 0536.68041 MR 85b:03041","DOI":"10.1016\/0022-0000(83)90014-4"},{"key":"14","doi-asserted-by":"crossref","unstructured":"Hemaspaandra, E., \u201cComplexity transfer for modal logic,\u201d pp. 164\u2013173 in <i>Proceedings of the Ninth IEEE Symposium on Logic In Computer Science (LICS'94)<\/i>, IEEE Computer Society Press, Los Alamitos, 1994.","DOI":"10.1109\/LICS.1994.316074"},{"key":"15","unstructured":"Hughes, G., and M. Cresswell, <i>A Companion to Modal Logic<\/i>, Methuen, London, 1984. Zbl 0625.03005 MR 86j:03014"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Kracht, K., and F. Wolter, \u201cProperties of independently axiomatizable bimodal logics,\u201d <i>The Journal of Symbolic Logic<\/i>, vol. 56 (1991), pp. 1469\u20131485. Zbl 0743.03013 MR 93c:03021","DOI":"10.2307\/2275487"},{"key":"17","doi-asserted-by":"crossref","unstructured":"Ladner, R., \u201cThe computational complexity of provability in systems of modal logic,\u201d <i>SIAM Journal on Computing<\/i>, vol. 6 (1977), pp. 467\u2013480. Zbl 0373.02025 MR 56:8326","DOI":"10.1137\/0206033"},{"key":"18","doi-asserted-by":"crossref","unstructured":"Ladner, R., N. Lynch, and A. Selman, \u201cA comparison of polynomial time reductions,\u201d <i>Theoretical Computer Science<\/i>, vol. 1 (1975), pp. 103\u2013123. Zbl 0321.68039 MR 52:16116","DOI":"10.1016\/0304-3975(75)90016-X"},{"key":"19","doi-asserted-by":"crossref","unstructured":"Ladner, R., and J. Reif, \u201cThe logics of distributed protocols,\u201d pp. 207\u2013221 in <i>Theoretical Aspects of Reasoning About Knowledge: Proceedings of the 1986 Conference<\/i>, Morgan Kaufmann, Los Altos, 1986. MR 88k:03008","DOI":"10.1016\/B978-0-934613-04-0.50016-8"},{"key":"20","doi-asserted-by":"crossref","unstructured":"Lewis, H., \u201cComplexity of solvable cases of the decision problem for the predicate calculus,\u201d pp. 35\u201347 in <i>Proceedings of the 19th IEEE Symposium on Foundations of Computer Science<\/i>, IEEE Computer Society Press, Los Alamitos, 1978. hrefhttp:\/\/www.ams.org\/mathscinet-getitem?mr=80e:03041MR 80e:03041","DOI":"10.1109\/SFCS.1978.9"},{"key":"21","doi-asserted-by":"crossref","unstructured":"Parikh, R., \u201cPropositional logics of programs: systems, models, and complexity,\u201d pp. 186\u2013192 in <i>Seventh Annual ACM Symposium on Principles of Programming Languages<\/i>, ACM Press, New York, 1980.","DOI":"10.1145\/567446.567464"},{"key":"22","doi-asserted-by":"crossref","unstructured":"Pratt, V., \u201cModels of program logics,\u201d pp. 115\u2013122 in <i>Proceedings of the 20th IEEE Symposium on Foundations of Computer Science<\/i>, IEEE Computer Society Press, Los Alamitos, 1979.","DOI":"10.1109\/SFCS.1979.24"},{"key":"23","doi-asserted-by":"crossref","unstructured":"Robinson, R., \u201cUndecidability and nonperiodicity for tilings of the plane,\u201d <i>Inventiones Mathematic\u00e6<\/i>, vol. 12 (1971), pp. 177\u2013209. Zbl 0197.4680 MR 45:6626","DOI":"10.1007\/BF01418780"},{"key":"24","doi-asserted-by":"crossref","unstructured":"Sahlqvist, H., \u201cCompleteness and correspondence in the first and second order semantics for modal logics,\u201d pp. 110\u2013143 in <i>Proceedings of the third Scandinavian Logic Symposium<\/i>, North-Holland, Amsterdam, 1975. Zbl 0319.02018 MR 52:7855","DOI":"10.1016\/S0049-237X(08)70728-6"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Sistla, A., and E. Clarke, \u201cThe complexity of propositional linear temporal logics,\u201d <i>Journal of the ACM<\/i>, vol. 32 (1985), pp. 733\u2013749. Zbl 0632.68034 MR 87j:68077","DOI":"10.1145\/3828.3837"},{"key":"26","unstructured":"Spaan, E., \u201cNexttime is not necessary,\u201d pp. 241\u2013256 in <i>Proceedings of the Third Conference on Theoretical Aspects of Reasoning About Knowledge<\/i>, Morgan Kaufmann, Los Altos, 1990."},{"key":"27","unstructured":"van Emde Boas, P., \u201cDominoes are forever,\u201d pp. 75\u201395 in <i>1st GTI Workshop<\/i>, Paderborn, 1983."}],"container-title":["Notre Dame Journal of Formal Logic"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/journalArticle\/Download?urlid=10.1305\/ndjfl\/1040046086","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,11]],"date-time":"2024-12-11T21:49:49Z","timestamp":1733953789000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/notre-dame-journal-of-formal-logic\/volume-37\/issue-2\/The-Price-of-Universality\/10.1305\/ndjfl\/1040046086.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,4,1]]},"references-count":27,"journal-issue":{"issue":"2","published-online":{"date-parts":[[1996,4,1]]}},"URL":"https:\/\/doi.org\/10.1305\/ndjfl\/1040046086","relation":{},"ISSN":["0029-4527"],"issn-type":[{"type":"print","value":"0029-4527"}],"subject":[],"published":{"date-parts":[[1996,4,1]]}}}