{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:25:33Z","timestamp":1740108333253,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T00:00:00Z","timestamp":1659571200000},"content-version":"vor","delay-in-days":3,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["FE 560 \/ 9-1"],"award-info":[{"award-number":["FE 560 \/ 9-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The regular intersection emptiness problem for a decision problem<jats:italic>P<\/jats:italic>(<jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\textit{int}}_{{\\mathrm {Reg}}}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>int<\/mml:mi><mml:mi>Reg<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>(<jats:italic>P<\/jats:italic>)) is to decide whether a potentially infinite regular set of encoded<jats:italic>P<\/jats:italic>-instances contains a positive one. Since<jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\textit{int}}_{{\\mathrm {Reg}}}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>int<\/mml:mi><mml:mi>Reg<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>(<jats:italic>P<\/jats:italic>) is decidable for some NP-complete problems and undecidable for others, its investigation provides insights in the nature of NP-complete problems. Moreover, the decidability of the<jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\textit{int}}_{{\\mathrm {Reg}}}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>int<\/mml:mi><mml:mi>Reg<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-problem is usually achieved by exploiting the regularity of the set of instances; thus, it also establishes a connection to formal language and automata theory. We consider the<jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\textit{int}}_{{\\mathrm {Reg}}}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>int<\/mml:mi><mml:mi>Reg<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-problem for the well-known NP-complete problem<jats:sc>Integer Linear Programming<\/jats:sc>(<jats:sc>ILP<\/jats:sc>). It is shown that any DFA that describes a set of<jats:sc>ILP<\/jats:sc>-instances (in a natural encoding) can be reduced to a finite core of instances that contains a positive one if and only if the original set of instances did. This result yields the decidability of<jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\textit{int}}_{{\\mathrm {Reg}}}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>int<\/mml:mi><mml:mi>Reg<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>(<jats:sc>ILP<\/jats:sc>).<\/jats:p>","DOI":"10.1007\/s00236-022-00429-x","type":"journal-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T18:02:37Z","timestamp":1659636157000},"page":"505-519","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the decidability of finding a positive ILP-instance in a regular set of ILP-instances"],"prefix":"10.1007","volume":"59","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3097-3906","authenticated-orcid":false,"given":"Petra","family":"Wolf","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,4]]},"reference":[{"issue":"11","key":"429_CR1","doi-asserted-by":"publisher","first-page":"1096","DOI":"10.1016\/j.ic.2008.06.007","volume":"207","author":"T Anderson","year":"2009","unstructured":"Anderson, T., Loftus, J., Rampersad, N., Santean, N., Shallit, J.: Detecting palindromes, patterns and borders in regular languages. Inf. Comput. 207(11), 1096\u20131118 (2009)","journal-title":"Inf. Comput."},{"key":"429_CR2","unstructured":"Bodlaender, H., Heggernes, P., Lokshtanov, D.: Graph Modification Problems (Dagstuhl Seminar 14071) (2014)"},{"key":"429_CR3","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151\u2013158. ACM (1971)","DOI":"10.1145\/800157.805047"},{"issue":"1","key":"429_CR4","first-page":"2:1","volume":"3","author":"G Cormode","year":"2007","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. ACM Trans. Algorithms (TALG) 3(1), 2:1-2:19 (2007)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"429_CR5","unstructured":"Corporation, I.: IBM CPLEX Optimizer. https:\/\/www.ibm.com\/analytics\/cplex-optimizer"},{"key":"429_CR6","doi-asserted-by":"crossref","unstructured":"Diekert, V., Fernau, H., Wolf, P.: Properties of graphs specified by a regular language. In: Moreira, N., Reis, R. (eds.) 25th International Conference on Developments in Language Theory, DLT 2021, Porto, Portugal, August 16-20, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12811, pp. 117\u2013129. Springer (2021)","DOI":"10.1007\/978-3-030-81508-0_10"},{"key":"429_CR7","doi-asserted-by":"crossref","unstructured":"Eiben, E., Ganian, R., Knop, D., Ordyniak, S.: Unary integer linear programming with structural restrictions. In: Proceedings of the twenty-seventh international joint conference on artificial intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pp. 1284\u20131290 (2018)","DOI":"10.24963\/ijcai.2018\/179"},{"key":"429_CR8","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.artint.2017.12.006","volume":"257","author":"R Ganian","year":"2018","unstructured":"Ganian, R., Ordyniak, S.: The complexity landscape of decompositional parameters for ILP. Artif. Intell. 257, 61\u201371 (2018)","journal-title":"Artif. Intell."},{"issue":"1","key":"429_CR9","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s10044-008-0141-y","volume":"13","author":"X Gao","year":"2010","unstructured":"Gao, X., Xiao, B., Tao, D., Li, X.: A survey of graph edit distance. Pattern Anal. Appl. 13(1), 113\u2013129 (2010)","journal-title":"Pattern Anal. Appl."},{"key":"429_CR10","doi-asserted-by":"crossref","unstructured":"G\u00fcler, D., Krebs, A., Lange, K.J., Wolf, P.: Deciding regular intersection emptiness of complete problems for PSPACE and the polynomial hierarchy. In: International Conference on Language and Automata Theory and Applications, pp. 156\u2013168. Springer (2018)","DOI":"10.1007\/978-3-319-77313-1_12"},{"key":"429_CR11","unstructured":"Gurobi: Gurobi Optimization. https:\/\/www.gurobi.com"},{"key":"429_CR12","unstructured":"Hlad\u00edk, M.: Interval linear programming: a survey. In: Linear Programming: New Frontiers in Theory and Applications, chap. 2, pp. 85\u2013120. Nova Science Publishers, New York (2012)"},{"key":"429_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68279-0","volume-title":"50 Years of Integer Programming 1958\u20132008: From the Early Years to the State-of-the-Art","author":"M J\u00fcnger","year":"2010","unstructured":"J\u00fcnger, M., Liebling, T.M., Naddef, D., Nemhauser, G.L., Pulleyblank, W.R., Reinelt, G., Rinaldi, G., Wolsey, L.A.: 50 Years of Integer Programming 1958\u20132008: From the Early Years to the State-of-the-Art. Springer, Berlin (2010)"},{"key":"429_CR14","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a Symposium on the Complexity of Computer Computations, Held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA. The IBM Research Symposia Series, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"429_CR15","unstructured":"Lange, K.J., Reinhardt, K.: Set automata. In: Combinatorics, Complexity and Logic; Proceedings of the DMTCS\u201996. Citeseer (1996)"},{"key":"429_CR16","doi-asserted-by":"crossref","unstructured":"Lempitsky, V.S., Kohli, P., Rother, C., Sharp, T.: Image segmentation with a bounding box prior. In: ICCV, pp. 277\u2013284. Citeseer (2009)","DOI":"10.1109\/ICCV.2009.5459262"},{"key":"429_CR17","doi-asserted-by":"crossref","unstructured":"Li, H.: Two-view motion segmentation from linear programming relaxation. In: Computer Vision and Pattern Recognition, pp. 1\u20138. IEEE (2007)","DOI":"10.1109\/CVPR.2007.382975"},{"issue":"4","key":"429_CR18","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1109\/TST.2014.6867517","volume":"19","author":"Y Liu","year":"2014","unstructured":"Liu, Y., Wang, J., Guo, J.: An overview of kernelization algorithms for graph modification problems. Tsinghua Sci. Technol. 19(4), 346\u2013357 (2014)","journal-title":"Tsinghua Sci. Technol."},{"key":"429_CR19","unstructured":"lp_solve: lpSolve. http:\/\/lpsolve.sourceforge.net\/5.5\/"},{"key":"429_CR20","unstructured":"MathWorks: Optimization Toolbox. https:\/\/de.mathworks.com\/products\/optimization.html"},{"key":"429_CR21","doi-asserted-by":"crossref","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization. Wiley Interscience Series in Discrete Mathematics and Optimization","author":"GL Nemhauser","year":"1988","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley Interscience Series in Discrete Mathematics and Optimization. Wiley, Hoboken (1988)"},{"key":"429_CR22","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"CH Papadimitriou","year":"1998","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity, 2nd edn. Prentice-Hall, Hoboken (1998)","edition":"2"},{"key":"429_CR23","doi-asserted-by":"crossref","unstructured":"Rubtsov, A.A.: Regular realizability problems and regular languages. CoRR abs\/1503.05879 (2015)","DOI":"10.1007\/978-3-319-19225-3_22"},{"key":"429_CR24","unstructured":"Rubtsov, A.A., Vyalyi, M.N.: Regular realizability problems and models of a generalized nondeterminism. CoRR abs\/1105.5894 (2011)"},{"key":"429_CR25","doi-asserted-by":"crossref","unstructured":"Rubtsov, A.A., Vyalyi, M.N.: Automata equipped with auxiliary data structures and regular realizability problems. In: Han, Y., Ko, S. (eds.) Proceedings of 23rd IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2021, Virtual Event, September 5, 2021. Lecture Notes in Computer Science, vol. 13037, pp. 150\u2013162. Springer (2021)","DOI":"10.1007\/978-3-030-93489-7_13"},{"key":"429_CR26","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1999","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, Hoboken (1999)"},{"key":"429_CR27","doi-asserted-by":"crossref","unstructured":"Tarasov, S.P., Vyalyi, M.N.: Orbits of linear maps and regular languages. In: Computer Science\u2013Theory and Applications: 6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011, Proceedings, pp. 305\u2013316 (2011)","DOI":"10.1007\/978-3-642-20712-9_24"},{"key":"429_CR28","doi-asserted-by":"crossref","unstructured":"van Emde\u00a0Boas, P.: The Convenience of Tilings. Lecture Notes in Pure and Applied Mathematics, pp. 331\u2013363 (1997)","DOI":"10.1201\/9780429187490-12"},{"key":"429_CR29","doi-asserted-by":"crossref","unstructured":"Vyalyi, M.N.: On models of a nondeterministic computation. In: Computer Science\u2013Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings, pp. 334\u2013345 (2009)","DOI":"10.1007\/978-3-642-03351-3_31"},{"issue":"4","key":"429_CR30","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1134\/S003294601104003X","volume":"47","author":"MN Vyalyi","year":"2011","unstructured":"Vyalyi, M.N.: On regular realizability problems. Probl. Inf. Transm. 47(4), 342\u2013352 (2011)","journal-title":"Probl. Inf. Transm."},{"issue":"3","key":"429_CR31","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1134\/S0032946013030058","volume":"49","author":"MN Vyalyi","year":"2013","unstructured":"Vyalyi, M.N.: On expressive power of regular realizability problems. Probl. Inf. Transm. 49(3), 276\u2013291 (2013)","journal-title":"Probl. Inf. Transm."},{"issue":"4","key":"429_CR32","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1134\/S0032946015040043","volume":"51","author":"MN Vyalyi","year":"2015","unstructured":"Vyalyi, M.N., Rubtsov, A.A.: On regular realizability problems for context-free languages. Probl. Inf. Transm. 51(4), 349\u2013360 (2015)","journal-title":"Probl. Inf. Transm."},{"key":"429_CR33","volume-title":"Computational Complexity","author":"K Wagner","year":"1986","unstructured":"Wagner, K., Wechsung, G.: Computational Complexity. Springer, Berlin (1986)"},{"issue":"1","key":"429_CR34","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"RA Wagner","year":"1974","unstructured":"Wagner, R.A., Fischer, M.J.: The string-to-string correction problem. J. ACM 21(1), 168\u2013173 (1974)","journal-title":"J. ACM"},{"key":"429_CR35","unstructured":"Wolf, P.: Decidability of the Regular Intersection Emptiness Problem. Master\u2019s thesis, Wilhelm Schickhard Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen (2018)"},{"key":"429_CR36","doi-asserted-by":"crossref","unstructured":"Wolf, P.: On the decidability of finding a positive ILP-instance in a regular set of ILP-instances. In: Hospod\u00e1r, M., Jir\u00e1skov\u00e1, G., Konstantinidis, S. (eds.) Descriptional Complexity of Formal Systems: 21st IFIP WG 1.02 International Conference, DCFS 2019, Ko\u0161ice, Slovakia, July 17-19, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11612, pp. 272\u2013284. Springer (2019)","DOI":"10.1007\/978-3-030-23247-4_21"},{"key":"429_CR37","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2021.11.006","volume":"899","author":"P Wolf","year":"2022","unstructured":"Wolf, P.: From decidability to undecidability by considering regular sets of instances. Theor. Comput. Sci. 899, 25\u201338 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"429_CR38","unstructured":"Wolf, P., Fernau, H.: Regular intersection emptiness of graph problems: finding a needle in a haystack of graphs with the help of automata. CoRR. https:\/\/arxiv.org\/abs\/2003.05826 (2020)"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-022-00429-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-022-00429-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-022-00429-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,25]],"date-time":"2023-11-25T09:28:21Z","timestamp":1700904501000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-022-00429-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["429"],"URL":"https:\/\/doi.org\/10.1007\/s00236-022-00429-x","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2022,8]]},"assertion":[{"value":"27 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}