{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T07:27:42Z","timestamp":1750318062870},"reference-count":24,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p> The satisfiability problem of the branching time logic CTL is studied in terms of computational complexity. Tight upper and lower bounds are provided for each temporal operator fragment. In parallel, the minimal model size is studied with a suitable notion of minimality. Thirdly, flat CTL is investigated, i.e., formulas with very low temporal operator nesting depth. A sharp dichotomy is shown in terms of complexity and minimal models: Temporal depth one has low expressive power, while temporal depth two is equivalent to full CTL. <\/jats:p>","DOI":"10.1142\/s0129054118500028","type":"journal-article","created":{"date-parts":[[2018,3,20]],"date-time":"2018-03-20T02:20:23Z","timestamp":1521512423000},"page":"17-61","source":"Crossref","is-referenced-by-count":1,"title":["Quirky Quantifiers: Optimal Models and Complexity of Computation Tree Logic"],"prefix":"10.1142","volume":"29","author":[{"given":"Martin","family":"L\u00fcck","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Theoretische Informatik, Gottfried Wilhelm Leibniz Universit\u00e4t, Appelstra\u00dfe 4, 30167 Hannover, Germany"}]}],"member":"219","published-online":{"date-parts":[[2018,3,19]]},"reference":[{"key":"S0129054118500028BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88074-1.50021-4"},{"key":"S0129054118500028BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90001-7"},{"key":"S0129054118500028BIB003","doi-asserted-by":"publisher","DOI":"10.1145\/4904.4999"},{"key":"S0129054118500028BIB004","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-7(2:12)2011"},{"key":"S0129054118500028BIB005","volume-title":"SIGACT News","author":"B\u00f6hler E.","year":"2003"},{"key":"S0129054118500028BIB006","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"S0129054118500028BIB007","doi-asserted-by":"publisher","DOI":"10.1145\/5397.5399"},{"key":"S0129054118500028BIB008","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"S0129054118500028BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/BF02124750"},{"key":"S0129054118500028BIB010","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3094"},{"key":"S0129054118500028BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90046-1"},{"key":"S0129054118500028BIB012","volume-title":"Finite Model Theory and Its Applications. Texts in Theoretical Computer Science. An EATCS Series","author":"Gr\u00e4del E.","year":"2005"},{"key":"S0129054118500028BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(95)00018-A"},{"key":"S0129054118500028BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.10.011"},{"key":"S0129054118500028BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17364-6"},{"key":"S0129054118500028BIB016","doi-asserted-by":"publisher","DOI":"10.1137\/0206033"},{"key":"S0129054118500028BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744287"},{"key":"S0129054118500028BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-2464(07)80006-1"},{"key":"S0129054118500028BIB019","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054109006954"},{"key":"S0129054118500028BIB022","volume-title":"On The Two-Valued Iterative Systems of Mathematical Logic","author":"Post E. L.","year":"1941"},{"key":"S0129054118500028BIB023","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90061-6"},{"key":"S0129054118500028BIB024","volume-title":"Time and Modality","author":"Prior A. N.","year":"1957"},{"key":"S0129054118500028BIB025","first-page":"393","volume-title":"Advances in Modal Logic","author":"Schnoebelen P.","year":"2002"},{"key":"S0129054118500028BIB026","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3837"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118500028","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:00:50Z","timestamp":1565092850000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118500028"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":24,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2018,3,19]]},"published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1142\/S0129054118500028"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118500028","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}