On the decidability of finding a positive ILP-instance in a regular set of ILP-instances
Author:
Open Access
- 4 August 2022
- journal article
- research article
- Published by Springer Nature in Acta Informatica
- Vol. 59 (4) , 505-519
Abstract
The regular intersection emptiness problem for a decision problemP( $${{\textit{int}}_{{\mathrm {Reg}}}}$$ (P)) is to decide whether a potentially infinite regular set of encodedP-instances contains a positive one. Since $${{\textit{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 $${{\textit{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 $${{\textit{int}}_{{\mathrm {Reg}}}}$$ -problem for the well-known NP-complete problemInteger Linear Programming(ILP). It is shown that any DFA that describes a set ofILP-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 $${{\textit{int}}_{{\mathrm {Reg}}}}$$ (ILP).
Keywords
Funding Information
- Deutsche Forschungsgemeinschaft (FE 560 / 9-1)
This publication has 23 references indexed in Scilit:
- Regular Realizability Problems and Context-Free Languages2015
- On expressive power of regular realizability problemsProblems of Information Transmission, 2013
- On regular realizability problemsProblems of Information Transmission, 2011
- Orbits of Linear Maps and Regular Languages2011
- Detecting palindromes, patterns and borders in regular languagesInformation and Computation, 2009
- A survey of graph edit distancePattern Analysis and Applications, 2009
- On Models of a Nondeterministic ComputationLecture Notes in Computer Science, 2009
- Two-View Motion Segmentation from Linear Programming Relaxation2007
- The String-to-String Correction ProblemJournal of the ACM, 1974
- The complexity of theorem-proving procedures1971