{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T09:49:45Z","timestamp":1764841785871,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319155784"},{"type":"electronic","value":"9783319155791"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-15579-1_37","type":"book-chapter","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T08:36:13Z","timestamp":1424680573000},"page":"473-485","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity"],"prefix":"10.1007","author":[{"given":"Georg","family":"Bachmeier","sequence":"first","affiliation":[]},{"given":"Michael","family":"Luttenberger","sequence":"additional","affiliation":[]},{"given":"Maximilian","family":"Schlund","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"37_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1007\/978-3-540-85361-9_29","volume-title":"CONCUR 2008 - Concurrency Theory","author":"MF Atig","year":"2008","unstructured":"Atig, M.F., Bouajjani, A., Touili, T.: On the Reachability Analysis of Acyclic Networks of Pushdown Systems. In: van Breugel, F., Chechik, M. (eds.) CONCUR 2008. LNCS, vol. 5201, pp. 356\u2013371. Springer, Heidelberg (2008)"},{"key":"37_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/978-3-540-70583-3_34","volume-title":"Automata, Languages and Programming","author":"R Axelsson","year":"2008","unstructured":"Axelsson, R., Heljanko, K., Lange, M.: Analyzing Context-Free Grammars Using an Incremental SAT Solver. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 410\u2013422. Springer, Heidelberg (2008)"},{"key":"37_CR3","unstructured":"Bachmeier, G., Luttenberger, M., Schlund, M.: Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity. CoRR abs\/1410.2737 (2014). http:\/\/arxiv.org\/abs\/1410.2737"},{"key":"37_CR4","first-page":"143","volume":"14","author":"Y Bar-Hillel","year":"1961","unstructured":"Bar-Hillel, Y., Perles, M., Shamir, E.: On Formal Properties of Simple Phrase Structure Grammars. Zeitschrift f\u00fcr Phonetik, Sprachwissenschaft und Kommunikationsforschung 14, 143\u2013172 (1961)","journal-title":"Zeitschrift f\u00fcr Phonetik, Sprachwissenschaft und Kommunikationsforschung"},{"issue":"3","key":"37_CR5","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1016\/j.scico.2009.11.002","volume":"75","author":"C Brabrand","year":"2010","unstructured":"Brabrand, C., Giegerich, R., M\u00f8ller, A.: Analyzing Ambiguity of Context-Free Grammars. Sci. Comput. Program. 75(3), 176\u2013191 (2010)","journal-title":"Sci. Comput. Program."},{"key":"37_CR6","first-page":"178","volume":"44","author":"B Courcelle","year":"1991","unstructured":"Courcelle, B.: On Constructing Obstruction Sets of Words. Bulletin of the EATCS 44, 178\u2013186 (1991)","journal-title":"Bulletin of the EATCS"},{"key":"37_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-319-08846-4_1","volume-title":"Implementation and Application of Automata","author":"J Esparza","year":"2014","unstructured":"Esparza, J., Luttenberger, M., Schlund, M.: FPsolve: A Generic Solver for Fixpoint Equations over Semirings. In: Holzer, M., Kutrib, M. (eds.) CIAA 2014. LNCS, vol. 8587, pp. 1\u201315. Springer, Heidelberg (2014)"},{"issue":"2","key":"37_CR8","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/s10703-011-0136-y","volume":"40","author":"P Ganty","year":"2012","unstructured":"Ganty, P., Majumdar, R., Monmege, B.: Bounded underapproximations. Formal Methods in System Design 40(2), 206\u2013231 (2012)","journal-title":"Formal Methods in System Design"},{"issue":"1","key":"37_CR9","first-page":"105","volume":"91","author":"H Gruber","year":"2009","unstructured":"Gruber, H., Holzer, M., Kutrib, M.: More on the Size of Higman-Haines Sets: Effective Constructions. Fundam. Inf. 91(1), 105\u2013121 (2009)","journal-title":"Fundam. Inf."},{"key":"37_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1007\/978-3-642-14162-1_39","volume-title":"Automata, Languages and Programming","author":"P Habermehl","year":"2010","unstructured":"Habermehl, P., Meyer, R., Wimmel, H.: The Downward-Closure of Petri Net Languages. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 466\u2013477. Springer, Heidelberg (2010)"},{"key":"37_CR11","doi-asserted-by":"crossref","unstructured":"Higman, G.: Ordering by Divisibility in Abstract Algebras. Proc. London Math. Soc. s3\u20132(1), 326\u2013336 (Jan 1952)","DOI":"10.1112\/plms\/s3-2.1.326"},{"key":"37_CR12","unstructured":"Lange, M., Lei\u00df, H.: To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm. Informatica Didactica 8 (2009)"},{"issue":"3","key":"37_CR13","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0012-365X(78)90156-5","volume":"21","author":"J van Leeuwen","year":"1978","unstructured":"van Leeuwen, J.: Effective constructions in well-partially-ordered free monoids. Discrete Mathematics 21(3), 237\u2013252 (1978)","journal-title":"Discrete Mathematics"},{"key":"37_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/978-3-642-28872-2_25","volume-title":"Fundamental Approaches to Software Engineering","author":"Z Long","year":"2012","unstructured":"Long, Z., Calin, G., Majumdar, R., Meyer, R.: Language-Theoretic Abstraction Refinement. In: de Lara, J., Zisman, A. (eds.) Fundamental Approaches to Software Engineering. LNCS, vol. 7212, pp. 362\u2013376. Springer, Heidelberg (2012)"},{"key":"37_CR15","series-title":"Text, Speech and Language Technology","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-94-015-9719-7_6","volume-title":"Robustness in Language and Speech Technology","author":"M Mohri","year":"2001","unstructured":"Mohri, M., Nederhof, M.J.: Regular Approximation of Context-Free Grammars through Transformation. In: Junqua, J.C., van Noord, G. (eds.) Robustness in Language and Speech Technology. Text, Speech and Language Technology, vol. 17, pp. 153\u2013163. Springer, Netherlands (2001)"},{"key":"37_CR16","unstructured":"Nederhof, M., Satta, G.: New Developments in Formal Languages and Applications. Studies in Computational Intelligence, pp. 229\u2013258. Springer, Heidelberg (2008)"},{"issue":"3","key":"37_CR17","doi-asserted-by":"crossref","first-page":"325","DOI":"10.3233\/FI-2010-252","volume":"99","author":"A Okhotin","year":"2010","unstructured":"Okhotin, A.: On the State Complexity of Scattered Substrings and Superstrings. Fundam. Inform. 99(3), 325\u2013338 (2010)","journal-title":"Fundam. Inform."},{"issue":"1\u20134","key":"37_CR18","doi-asserted-by":"crossref","first-page":"223","DOI":"10.3233\/FI-2012-680","volume":"116","author":"N Rampersad","year":"2012","unstructured":"Rampersad, N., Shallit, J., Xu, Z.: The Computational Complexity of Universality Problems for Prefixes, Suffixes, Factors, and Subwords of Regular Languages. Fundam. Inform. 116(1\u20134), 223\u2013236 (2012)","journal-title":"Fundam. Inform."},{"key":"37_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"692","DOI":"10.1007\/978-3-540-73420-8_60","volume-title":"Automata, Languages and Programming","author":"S Schmitz","year":"2007","unstructured":"Schmitz, S.: Conservative Ambiguity Detection in Context-Free Grammars. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 692\u2013703. Springer, Heidelberg (2007)"},{"key":"37_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/978-3-319-02654-1_9","volume-title":"Software Language Engineering","author":"N Vasudevan","year":"2013","unstructured":"Vasudevan, N., Tratt, L.: Detecting Ambiguity in Programming Language Grammars. In: Erwig, M., Paige, R.F., Van Wyk, E. (eds.) SLE 2013. LNCS, vol. 8225, pp. 157\u2013176. Springer, Heidelberg (2013)"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-15579-1_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T05:07:15Z","timestamp":1674191235000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-15579-1_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319155784","9783319155791"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-15579-1_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 February 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}