{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:27Z","timestamp":1740109407022,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,7,25]],"date-time":"2016-07-25T00:00:00Z","timestamp":1469404800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s00224-016-9694-0","type":"journal-article","created":{"date-parts":[[2016,7,25]],"date-time":"2016-07-25T02:53:41Z","timestamp":1469415221000},"page":"438-472","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Boolean Closed Full Trios and Rational Kripke Frames"],"prefix":"10.1007","volume":"60","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6421-4388","authenticated-orcid":false,"given":"Georg","family":"Zetzsche","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dietrich","family":"Kuske","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,25]]},"reference":[{"key":"9694_CR1","doi-asserted-by":"crossref","unstructured":"Barcel\u00f3, P., Figueira, D., Libkin, L.: Graph Logics with Rational Relations and the Generalized Intersection Problem. In: Proceedings of the 27Th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS 2012), pp 115\u2013124. IEEE Computer Society (2012)","DOI":"10.1109\/LICS.2012.23"},{"key":"9694_CR2","doi-asserted-by":"crossref","unstructured":"Bekker, W., Goranko, V.: Symbolic Model Checking of Tense Logics on Rational Kripke Models. In: Selected Papers of the International Conference on Infinity and Logic in Computation (ILC 2007), Lecture Notes in Computer Science, pp 2\u201320. Springer-Verlag (2009)","DOI":"10.1007\/978-3-642-03092-5_2"},{"key":"9694_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-663-09367-1","volume-title":"Transductions and Context-Free Languages","author":"J Berstel","year":"1979","unstructured":"Berstel, J.: Transductions and Context-Free Languages. Teubner, Stuttgart (1979)"},{"key":"9694_CR4","doi-asserted-by":"crossref","unstructured":"Blackburn, P., De Rijke, M., Venema, Y.: Modal logic. Cambridge University Press (2001)","DOI":"10.1017\/CBO9781107050884"},{"issue":"1","key":"9694_CR5","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/322047.322050","volume":"25","author":"RV Book","year":"1978","unstructured":"Book, R.V.: Simple representations of certain classes of languages. J. ACM 25 (1), 23\u201331 (1978)","journal-title":"J. ACM"},{"key":"9694_CR6","doi-asserted-by":"crossref","unstructured":"Carayol, A., Morvan, C.: On Rational Trees. In: Proceedings of the 15Th Annual EACSL Conference on Computer Science Logic (CSL 2006), Volume 4207 of Lecture Notes in Computer Science, pp 225\u2013239. Springer-Verlag (2006)","DOI":"10.1007\/11874683_15"},{"issue":"1","key":"9694_CR7","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1006\/inco.2001.3139","volume":"176","author":"O Carton","year":"2002","unstructured":"Carton, O., Thomas, W.: The monadic theory of morphic infinite words and generalizations. Inf. Comput. 176(1), 51\u201365 (2002)","journal-title":"Inf. Comput."},{"key":"9694_CR8","doi-asserted-by":"crossref","DOI":"10.1016\/S0049-237X(08)72023-8","volume-title":"The algebraic theory of context-free languages","author":"N Chomsky","year":"1963","unstructured":"Chomsky, N., Sch\u00fctzenberger, M.-P.: The algebraic theory of context-free languages. North-Holland, Amsterdam (1963)"},{"issue":"2","key":"9694_CR9","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(82)90009-3","volume":"20","author":"W Damm","year":"1982","unstructured":"Damm, W.: The IO- and OI-hierarchies. Theor. Comput. Sci. 20(2), 95\u2013207 (1982)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"9694_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(86)80016-X","volume":"71","author":"W Damm","year":"1986","unstructured":"Damm, W., Goerdt, A.: An automata-theoretical characterization of the OI-hierarchy. Inf. Control. 71(1\u20132), 1\u201332 (1986)","journal-title":"Inf. Control."},{"key":"9694_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-74932-2","volume-title":"Regulated rewriting in formal language theory","author":"J Dassow","year":"1989","unstructured":"Dassow, J., P\u0103un, G.: Regulated rewriting in formal language theory. Springer-verlag, Berlin Heidelberg (1989)"},{"issue":"2","key":"9694_CR12","doi-asserted-by":"crossref","first-page":"169","DOI":"10.2307\/2269808","volume":"31","author":"CC Elgot","year":"1966","unstructured":"Elgot, C.C., Rabin, M.O.: Decidability and undecidability of extensions of second (first) order theory of (generalized) successor. J. Symb. Log. 31(2), 169\u2013181 (1966)","journal-title":"J. Symb. Log."},{"issue":"3","key":"9694_CR13","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/322203.322211","volume":"27","author":"J Engelfriet","year":"1980","unstructured":"Engelfriet, J., Rozenberg, G.: Fixed point languages, equality languages, and representation of recursively enumerable languages. J. ACM 27(3), 499\u2013518 (1980)","journal-title":"J. ACM"},{"key":"9694_CR14","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/S0304-3975(01)00282-1","volume":"276","author":"H Fernau","year":"2002","unstructured":"Fernau, H., Stiebe, R.: Sequential grammars and automata with valences. Theor. Comput. Sci. 276, 377\u2013405 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9694_CR15","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0304-3975(93)90230-Q","volume":"108","author":"C Frougny","year":"1993","unstructured":"Frougny, C., Sakarovitch, J.: Synchronized rational relations of finite and infinite words. Theor. Comput. Sci. 108(1), 45\u201382 (1993)","journal-title":"Theor. Comput. Sci."},{"issue":"3\u20134","key":"9694_CR16","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s00236-007-0050-3","volume":"44","author":"G Geeraerts","year":"2007","unstructured":"Geeraerts, G., Raskin, J.-F., Van Begin, L.: Well-structured languages. Acta Inf. 44(3\u20134), 249\u2013288 (2007)","journal-title":"Acta Inf."},{"issue":"3","key":"9694_CR17","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/S0019-9958(73)90274-X","volume":"22","author":"S Ginsburg","year":"1973","unstructured":"Ginsburg, S., Goldstine, J.: Intersection-closed full AFL and the recursively enumerable languages. Inf. Control. 22(3), 201\u2013231 (1973)","journal-title":"Inf. Control."},{"issue":"3","key":"9694_CR18","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0304-3975(78)90020-8","volume":"7","author":"SA Greibach","year":"1978","unstructured":"Greibach, S.A.: Remarks on blind and partially blind one-way multicounter machines. Theor. Comput. Sci. 7(3), 311\u2013324 (1978)","journal-title":"Theor. Comput. Sci."},{"key":"9694_CR19","doi-asserted-by":"crossref","unstructured":"Harju, T., Karhum\u00e4ki, J., Krob, D.: Remarks on Generalized Post Correspondence Problem. In: Proceedings of the 13Th International Symposium on Theoretical Aspects of Computer Science (STACS 1996), Volume 1046 of Lecture Notes in Computer Science, pp 39\u201348. Springer-Verlag (1996)","DOI":"10.1007\/3-540-60922-9_4"},{"issue":"4","key":"9694_CR20","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1016\/S0022-0000(70)80018-6","volume":"4","author":"J Hartmanis","year":"1970","unstructured":"Hartmanis, J., Hopcroft, J.: What makes some language theory problems undecidable. J. Comput. Syst. Sci. 4(4), 368\u2013376 (1970)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9694_CR21","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/S0019-9958(80)90537-9","volume":"47","author":"D Haussler","year":"1980","unstructured":"Haussler, D., Zeiger, H.P.: Very special languages and representations of recursively enumerable languages via computation histories. Inf. Control. 47(3), 201\u2013212 (1980)","journal-title":"Inf. Control."},{"key":"9694_CR22","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation. Addison\u2013Wesley, Reading, MA (1979)"},{"issue":"2","key":"9694_CR23","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0890-5401(03)00087-7","volume":"185","author":"M Jantzen","year":"2003","unstructured":"Jantzen, M., Kurganskyy, A.: Refining the hierarchy of blind multicounter languages and twist-closed trios. Inf. Comput. 185(2), 159\u2013181 (2003)","journal-title":"Inf. Comput."},{"key":"9694_CR24","doi-asserted-by":"crossref","unstructured":"Khoussainov, B., Nerode, A.: Automatic Presentations of Structures. In: LCC: International Workshop on Logic and Computational Complexity, Volume 960 of Lecture Notes in Computer Science, pp 367\u2013392. Springer-Verlag (1995)","DOI":"10.1007\/3-540-60178-3_93"},{"key":"9694_CR25","doi-asserted-by":"crossref","unstructured":"Kleene, S. C.: Representation of events in nerve nets and finite automata. In: Shannon, C.E., McCarthy, J. (eds.) Automata Studies, pp 3\u201341. Princeton University Press, Princeton, NJ (1956)","DOI":"10.1515\/9781400882618-002"},{"key":"9694_CR26","unstructured":"Lohrey, M., Zetzsche, G.: On Boolean closed full trios and rational Kripke frames. In: Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), volume 25 of Leibniz International Proceedings in Informatics (LIPIcs), pp 530-541. Schloss DagstuhlLeibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2014)"},{"issue":"3","key":"9694_CR27","doi-asserted-by":"crossref","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"M Minsky","year":"1961","unstructured":"Minsky, M.: Recursive unsolvability of Post\u2019s problem of `tag\u2019 and other topics in theory of Turing machines. Ann. Math. 74(3), 437\u2013455 (1961)","journal-title":"Ann. Math."},{"key":"9694_CR28","doi-asserted-by":"crossref","unstructured":"Morvan, C.: On rational graphs. In: Proceedings of the 3Rd International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2000), Volume 2303 of Lecture Notes in Computer Science, pp 252\u2013266. Springer-Verlag (2000)","DOI":"10.1007\/3-540-46432-8_17"},{"key":"9694_CR29","doi-asserted-by":"crossref","unstructured":"Morvan, C., Stirling, C.: Rational Graphs Trace Context-Sensitive Languages. In: Proceedings of the 26Th International Symposium on Mathematical Foundations of Computer Science (MFCS 2001), Volume 2136 of Lecture Notes in Computer Science, pp 548\u2013559. Springer-Verlag (2001)","DOI":"10.1007\/3-540-44683-4_48"},{"issue":"1","key":"9694_CR30","doi-asserted-by":"crossref","first-page":"339","DOI":"10.5802\/aif.287","volume":"18","author":"M Nivat","year":"1968","unstructured":"Nivat, M.: Transductions des langages de Chomsky. Ann. l\u2019Institut Fourier 18 (1), 339\u2013455 (1968)","journal-title":"Ann. l\u2019Institut Fourier"},{"key":"9694_CR31","doi-asserted-by":"crossref","unstructured":"Pin, J.-\u00c9., Sakarovitch, J.: Some Operations and Transductions that Preserve Rationality. In: Proceedings of the 6Th GI Conference, Volume 145 of Lecture Notes in Computer Science, pp 277\u2013288. Springer-Verlag (1983)","DOI":"10.1007\/BFb0009652"},{"key":"9694_CR32","doi-asserted-by":"crossref","first-page":"870","DOI":"10.1016\/j.ic.2006.12.004","volume":"205","author":"A Rabinovich","year":"2007","unstructured":"Rabinovich, A.: On decidability of monadic logic of order over the naturals extended by monadic predicates. Inf. Comput. 205, 870\u2013889 (2007)","journal-title":"Inf. Comput."},{"key":"9694_CR33","doi-asserted-by":"crossref","unstructured":"Rabinovich, A., Thomas, W.: Decidable theories of the ordering of natural numbers with unary predicates. In: Proceedings of the 15th Annual EACSL Conference on Computer Science Logic (CSL 2006), volume 4207 of Lecture Notes in Computer Science, pp 562-574. Springer-Verlag, Berlin Heidelberg (2006)","DOI":"10.1007\/11874683_37"},{"key":"9694_CR34","unstructured":"Reinhardt, K.: The \u201ctrio-zoo\u201d\u2013classes of formal languages generated from one language by rational transduction. Unpublished manuscript"},{"key":"9694_CR35","unstructured":"Render, E.: Rational monoid and semigroup automata. PhD Thesis, University of Manchester (2010)"},{"key":"9694_CR36","unstructured":"Rogers, H.: Theory of recursive functions and effective computability. McGraw-Hill (1968)"},{"key":"9694_CR37","doi-asserted-by":"crossref","unstructured":"Seibert, S.: Quantifier hierarchies over word relations. In: Proceedings of the 5Th Annual EACSL Conference on Computer Science Logic (CSL 1991), Volume 626 of Lecture Notes in Computer Science, pp 329\u2013352. Springer-Verlag (1992)","DOI":"10.1007\/BFb0023779"},{"key":"9694_CR38","doi-asserted-by":"crossref","unstructured":"Semenov, A.: Decidability of monadic theories. In: Proceedings of the 11Th International Symposium on Mathematical Foundations of Computer Science (MFCS 1984), Volume 176 of Lecture Notes in Computer Science, pp 162\u2013175. Springer-Verlag (1984)","DOI":"10.1007\/BFb0030296"},{"key":"9694_CR39","doi-asserted-by":"crossref","unstructured":"Thomas, W.: A Short Introduction to Infinite Automata. In: Proceedings of the 5Th International Conference on Developments in Language Theory (DLT 2001), Volume 2295 of Lecture Notes in Computer Science, pp 130\u2013144. Springer-Verlag (2001)","DOI":"10.1007\/3-540-46011-X_10"},{"key":"9694_CR40","doi-asserted-by":"crossref","unstructured":"Zetzsche, G.: On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids. In: Proceedings of the 38Th International Colloquium on Automata, Languages and Programming (ICALP 2011), Volume 6756 of Lecture Notes in Computer Science, pp 222\u2013233. Springer-Verlag (2011)","DOI":"10.1007\/978-3-642-22012-8_17"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9694-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9694-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9694-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9694-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T13:12:18Z","timestamp":1568207538000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9694-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,25]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["9694"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9694-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2016,7,25]]}}}