Reseña: A constructive theory of regular languages in Coq

Se ha publicado un artículo de razonamiento formalizado en Coq titulado A constructive theory of regular languages in Coq.

Sus autores son Christian Doczkal, Jan-Oliver Kaiser y Gert Smolka (de la Univ. de Sarre (en alemán: Saarland), Alemania).

Su resumen es

We present a formal constructive theory of regular languages consisting of about 1400 lines of Coq/Ssreflect. As representations we consider regular expressions, deterministic and nondeterministic automata, and Myhill and Nerode partitions. We construct computable functions translating between these representations and show that equivalence of representations is decidable. We also establish the usual closure properties, give a minimization algorithm for DFAs, and prove that minimal DFAs are unique up to state renaming. Our development profits much from Ssreflect’s support for finite types and graphs.

El código de las correspondientes teorías en Coq se encuentra aquí.