{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T19:47:23Z","timestamp":1789674443785,"version":"4.0.1"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030171261","type":"print"},{"value":"9783030171278","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T00:00:00Z","timestamp":1554422400000},"content-version":"vor","delay-in-days":94,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We consider a language together with the subword relation, the cover relation, and regular predicates. For such structures, we consider the extension of first-order logic by threshold- and modulo-counting quantifiers. Depending on the language, the used predicates, and the fragment of the logic, we determine four new combinations that yield decidable theories. These results extend earlier ones where only the language of all words without the cover relation and fragments of first-order logic were considered.<\/jats:p>","DOI":"10.1007\/978-3-030-17127-8_20","type":"book-chapter","created":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T11:11:46Z","timestamp":1554462706000},"page":"348-364","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Languages Ordered by the Subword Order"],"prefix":"10.1007","author":[{"given":"Dietrich","family":"Kuske","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Georg","family":"Zetzsche","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,4,5]]},"reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1002\/malq.19660120111","volume":"12","author":"H Apelt","year":"1966","unstructured":"Apelt, H.: Axiomatische Untersuchungen \u00fcber einige mit der Presburgerschen Arithmetik verwandten Systeme. Z. Math. Logik Grundlagen Math. 12, 131\u2013168 (1966)","journal-title":"Z. Math. Logik Grundlagen Math."},{"key":"20_CR2","doi-asserted-by":"publisher","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 Studienb\u00fccher, Stuttgart (1979)"},{"key":"20_CR3","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-642-01492-5_5","volume-title":"Handbook of Weighted Automata","author":"M Droste","year":"2009","unstructured":"Droste, M., Gastin, P.: Weighted automata and weighted logics. In: Droste, M., Kuich, W., Vogler, H. (eds.) Handbook of Weighted Automata, pp. 176\u2013211. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-01492-5_5"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"Finkel, A., Schnoebelen, Ph.: Well-structured transition systems everywhere! Theor. Comput. Sci. 256, 63\u201392 (2001)","DOI":"10.1016\/S0304-3975(00)00102-X"},{"key":"20_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/978-3-662-46678-0_24","volume-title":"Foundations of Software Science and Computation Structures","author":"P Habermehl","year":"2015","unstructured":"Habermehl, P., Kuske, D.: On Presburger arithmetic extended with modulo counting quantifiers. In: Pitts, A. (ed.) FoSSaCS 2015. LNCS, vol. 9034, pp. 375\u2013389. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46678-0_24"},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"Halfon, S., Schnoebelen, Ph., Zetzsche, G.: Decidability, complexity, and expressiveness of first-order logic over the subword ordering. In: Proceedings of the Thirty-Second Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS 2017), pp. 1\u201312. IEEE Computer Society (2017)","DOI":"10.1109\/LICS.2017.8005141"},{"key":"20_CR7","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1112\/plms\/s3-2.1.326","volume":"2","author":"G Higman","year":"1952","unstructured":"Higman, G.: Ordering by divisibility in abstract algebras. Proc. London Math. Soc. 2, 326\u2013336 (1952)","journal-title":"Proc. London Math. Soc."},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"Je\u017eek, J., McKenzie, R.: Definability in substructure orderings. I: finite semilattices. Algebra Univers. 61(1), 59\u201375 (2009)","DOI":"10.1007\/s00012-009-0002-6"},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"Je\u017eek, J., McKenzie, R.: Definability in substructure orderings. III: finite distributive lattices. Algebra Univers. 61(3\u20134), 283\u2013300 (2009)","DOI":"10.1007\/s00012-009-0021-3"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"Je\u017eek, J., McKenzie, R.: Definability in substructure orderings. IV: finite lattices. Algebra Univers. 61(3\u20134), 301\u2013312 (2009)","DOI":"10.1007\/s00012-009-0019-x"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Je\u017eek, J., McKenzie, R.: Definability in substructure orderings. II: finite ordered sets. Order 27(2), 115\u2013145 (2010)","DOI":"10.1007\/s11083-010-9141-9"},{"key":"20_CR12","unstructured":"Karandikar, P., Schnoebelen, Ph.: Decidability in the logic of subsequences and supersequences. In: Harsha, P., Ramalingam, G. (eds.) Proceedings of the 35th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics, vol. 45, pp. 84\u201397. Leibniz-Zentrum f\u00fcr Informatik (2015)"},{"key":"20_CR13","unstructured":"Karandikar, P., Schnoebelen, Ph.: The height of piecewise-testable languages with applications in logical complexity. In: Talbot, J.-M., Regnier, L. (eds.) Proceedings of the 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics, vol. 62, pp. 37:1\u201337:22 (2016)"},{"issue":"6","key":"20_CR14","doi-asserted-by":"publisher","first-page":"1135","DOI":"10.1093\/logcom\/exm038","volume":"17","author":"OV Kudinov","year":"2007","unstructured":"Kudinov, O.V., Selivanov, V.L.: Undecidability in the homomorphic quasiorder of finite labelled forests. J. Log. Comput. 17(6), 1135\u20131151 (2007)","journal-title":"J. Log. Comput."},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-642-13962-8_28","volume-title":"Programs, Proofs, Processes","author":"OV Kudinov","year":"2010","unstructured":"Kudinov, O.V., Selivanov, V.L., Yartseva, L.V.: Definability in the subword order. In: Ferreira, F., L\u00f6we, B., Mayordomo, E., Mendes Gomes, L. (eds.) CiE 2010. LNCS, vol. 6158, pp. 246\u2013255. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13962-8_28"},{"issue":"3","key":"20_CR16","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1016\/j.apal.2008.09.026","volume":"159","author":"OV Kudinov","year":"2009","unstructured":"Kudinov, O.V., Selivanov, V.L., Zhukov, A.V.: Definability in the h-quasiorder of labeled forests. Ann. Pure Appl. Logic 159(3), 318\u2013332 (2009)","journal-title":"Ann. Pure Appl. Logic"},{"key":"20_CR17","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1051\/ita:2005039","volume":"40","author":"D Kuske","year":"2006","unstructured":"Kuske, D.: Theories of orders on the set of words. Theor. Inf. Appl. 40, 53\u201374 (2006)","journal-title":"Theor. Inf. Appl."},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Kuske, D., Zetzsche, G.: Languages ordered by the subword order. CoRR, abs\/1901.02194 (2019)","DOI":"10.1007\/978-3-030-17127-8_20"},{"issue":"4","key":"20_CR19","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R Parikh","year":"1966","unstructured":"Parikh, R.: On context-free languages. J. ACM 13(4), 570\u2013581 (1966)","journal-title":"J. ACM"},{"key":"20_CR20","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-642-01492-5_4","volume-title":"Handbook of Weighted Automata","author":"J Sakarovitch","year":"2009","unstructured":"Sakarovitch, J.: Rational and recognisable power series. In: Droste, M., Kuich, W., Vogler, H. (eds.) Handbook of Weighted Automata, pp. 105\u2013174. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-01492-5_4"},{"issue":"3","key":"20_CR21","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/1071596.1071602","volume":"6","author":"N Schweikardt","year":"2005","unstructured":"Schweikardt, N.: Arithmetic, first-order logic, and counting quantifiers. ACM Trans. Comput. Log. 6(3), 634\u2013671 (2005)","journal-title":"ACM Trans. Comput. Log."},{"key":"20_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/978-3-662-54069-5_16","volume-title":"Logic and Its Applications","author":"RS Thinniyam","year":"2017","unstructured":"Thinniyam, R.S.: Definability of recursive predicates in the induced subgraph order. In: Ghosh, S., Prasad, S. (eds.) ICLA 2017. LNCS, vol. 10119, pp. 211\u2013223. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-54069-5_16"},{"issue":"3:21","key":"20_CR23","first-page":"1","volume":"14","author":"RS Thinniyam","year":"2018","unstructured":"Thinniyam, R.S.: Defining recursive predicates in graph orders. Logical Methods Comput. Sci. 14(3:21), 1\u201338 (2018)","journal-title":"Logical Methods Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-17127-8_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T17:06:15Z","timestamp":1757091975000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17127-8_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030171261","9783030171278"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17127-8_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"5 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Prague","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Czech Republic","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 April 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.etaps.org\/2019\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}