Regular inference as vertex coloring

This paper is concerned with the problem of supervised learning of deterministic finite state automata, in the technical sense of identification in the limit from complete data, by finding a minimal DFA consistent with a sample.We solve this problem by translating it in its entirety to a vertex coloring problem. Essentially, such a problem consists of two types of constraints that restrict the hypothesis space: inequivalence and equivalence constraints. The inequivalence constraints translate to the vertex coloring problem in a very natural way. The equivalence constraints however greatly complicate the translation to vertex coloring. In previous coloring-based translations, these were therefore encoded either dynamically by modifying the vertex coloring instance on-the-fly, or by encoding them as satisfiability problems.We provide the first translation that encodes both types of constraints together in a pure vertex coloring instance and prove the correctness of the construction. The coloring approach offers many opportunities for applying insights from combinatorial optimization and graph theory to regular inference. We immediately obtain new complexity bounds, as well as a family of new learning algorithms which can be used to obtain exact hypotheses as well as fast approximations.We also demonstrate that satisfying all inequivalence constraints in regular inference and vertex coloring are in some sense equally hard. This immediately implies that regular inference is not approximable within |S|1−ϵ|S|1−ϵ (|S||S| being the cardinality of the sample) for any ϵ>12, unless P=NPP=NP. It also indicates that solving only for inequivalence constraints is easier than the full regular inference problem.