%0 Conference Proceedings
%T On the Decidability of Finding a Positive ILP-Instance in a Regular Set of ILP-Instances
%+ Trier University
%A Wolf, Petra
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 21th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Košice, Slovakia
%Y Michal Hospodár
%Y Galina Jirásková
%Y Stavros Konstantinidis
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-11612
%P 272-284
%8 2019-07-17
%D 2019
%R 10.1007/978-3-030-23247-4_21
%K Deterministic finite automaton
%K Regular languages
%K Regular intersection emptiness problem
%K Decidability
%K Integer linear programming
%Z Computer Science [cs]Conference papers
%X The regular intersection emptiness problem for a decision problem P ($$ int_{\mathrm {Reg}} $$(P)) is to decide whether a potentially infinite regular set of encoded P-instances contains a positive one. Since $$ int_{\mathrm {Reg}} $$(P) 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 $$ int_{\mathrm {Reg}} $$-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 $$ int_{\mathrm {Reg}} $$-problem for the well-known NP-complete problem Integer Linear Programming (ILP). It is shown that any DFA that describes a set of ILP-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 $$ int_{\mathrm {Reg}} $$(ILP).
%G English
%Z TC 1
%Z WG 1.02
%2 https://inria.hal.science/hal-02387299/document
%2 https://inria.hal.science/hal-02387299/file/480958_1_En_21_Chapter.pdf
%L hal-02387299
%U https://inria.hal.science/hal-02387299
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-11612