{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T19:47:00Z","timestamp":1789674420585,"version":"4.0.1"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,7,9]],"date-time":"2018-07-09T00:00:00Z","timestamp":1531094400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100005304","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE40-0007"],"award-info":[{"award-number":["ANR-16-CE40-0007"]}],"id":[{"id":"10.13039\/501100005304","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Labex DigiCosme, Universit\u00e9 Paris-Saclay","award":["VERICONISS"],"award-info":[{"award-number":["VERICONISS"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,7,9]]},"DOI":"10.1145\/3209108.3209201","type":"proceedings-article","created":{"date-parts":[[2018,6,27]],"date-time":"2018-06-27T08:14:43Z","timestamp":1530087283000},"page":"929-938","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Separability by piecewise testable languages and downward closures beyond subwords"],"prefix":"10.1145","author":[{"given":"Georg","family":"Zetzsche","sequence":"first","affiliation":[{"name":"IRIF (Universit\u00e9 Paris-Diderot & CNRS), France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,7,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321488"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103001893"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/6400.6403"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11691372_22"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2006.24"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2934527"},{"key":"e_1_3_2_1_7_1","first-page":"178","article-title":"On constructing obstruction sets of words","volume":"44","author":"Courcelle Bruno","year":"1991","unstructured":"Bruno Courcelle. 1991. On constructing obstruction sets of words. Bulletin of the EATCS 44 (1991), 178--186.","journal-title":"Bulletin of the EATCS"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005079"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-22177-9_14"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Wojciech Czerwi\u0144ski Wim Martens Lorijn van Rooijen Marc Zeitoun and Georg Zetzsche. 2017. A Characterization for Decidable Separability by Piecewise Testable Languages. (2017). To appear in Discrete Mathematics & Theoretical Computer Science.","DOI":"10.23638\/DMTCS-19-4-1"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90124-4"},{"key":"e_1_3_2_1_12_1","volume-title":"Part I: Completions. In STACS","volume":"3","author":"Finkel Alain","year":"2009","unstructured":"Alain Finkel and Jean Goubault-Larrecq. 2009. Forward Analysis for WSTS, Part I: Completions. In STACS 2009, Vol. 3. 433--444."},{"key":"e_1_3_2_1_13_1","volume-title":"Deciding Piecewise Testable Separability for Regular Tree Languages. In ICALP","author":"Goubault-Larrecq Jean","year":"2016","unstructured":"Jean Goubault-Larrecq and Sylvain Schmitz. 2016. Deciding Piecewise Testable Separability for Regular Tree Languages. In ICALP 2016."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1880999.1881050"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837627"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(69)80111-0"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.326"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/322307.322317"},{"key":"e_1_3_2_1_19_1","unstructured":"Pierre Jullien. 1969. Contribution \u00e0 l\u00e9tude des types d'ordres dispers\u00e9s. Ph.D. Dissertation. Universit\u00e9 de Marseille."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90063-5"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.16"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28872-2_25"},{"key":"e_1_3_2_1_23_1","first-page":"38","article-title":"Multilevel stack automata","volume":"12","author":"Maslov A. N.","year":"1976","unstructured":"A. N. Maslov. 1976. Multilevel stack automata. Problems of Information Transmission 12, 1 (1976), 38--42.","journal-title":"Problems of Information Transmission"},{"key":"e_1_3_2_1_24_1","volume-title":"FSTTCS","volume":"24","author":"Place Thomas","year":"2013","unstructured":"Thomas Place, Lorijn van Rooijen, and Marc Zeitoun. 2013. Separating Regular Languages by Locally Testable and Locally Threshold Testable Languages. In FSTTCS 2013, Vol. 24. 363--375."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/646589.697341"},{"key":"e_1_3_2_1_26_1","unstructured":"Michael Sipser. 2013. Introduction to the Theory of Computation. Cengage Learning."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205019"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90156-5"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_35"},{"key":"e_1_3_2_1_30_1","volume-title":"STACS","volume":"30","author":"Zetzsche Georg","year":"2015","unstructured":"Georg Zetzsche. 2015. Computing downward closures for stacked counter automata. In STACS 2015, Vol. 30. 743--756."}],"event":{"name":"LICS '18: 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science","location":"Oxford United Kingdom","acronym":"LICS '18","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","IEEE-CS\\DATC IEEE Computer Society","EACSL European Association for Computer Science Logic"]},"container-title":["Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209108.3209201","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209108.3209201","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T07:31:06Z","timestamp":1781854266000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209108.3209201"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,9]]},"references-count":30,"alternative-id":["10.1145\/3209108.3209201","10.1145\/3209108"],"URL":"https:\/\/doi.org\/10.1145\/3209108.3209201","relation":{},"subject":[],"published":{"date-parts":[[2018,7,9]]},"assertion":[{"value":"2018-07-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}