Certifying DFA Bounds for Recognition and Separation

Autor:	Salomon Sickert, Orna Kupferman, Nir Lavee
Rok vydání:	2021
Předmět:	Determinacy TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Theoretical computer science Deterministic finite automaton Regular language DFA minimization Computer science Certification Gas meter prover Certificate Time complexity
Zdroj:	Automated Technology for Verification and Analysis ISBN: 9783030888848 ATVA
DOI:	10.1007/978-3-030-88885-5_4
Popis:	The automation of decision procedures makes certification essential. We suggest to use determinacy of turn-based two-player games with regular winning conditions in order to generate certificates for the number of states that a deterministic finite automaton (DFA) needs in order to recognize a given language. Given a language L and a bound k, recognizability of L by a DFA with k states is reduced to a game between Prover and Refuter. The interaction along the game then serves as a certificate. Certificates generated by Prover are minimal DFAs. Certificates generated by Refuter are faulty attempts to define the required DFA. We compare the length of offline certificates, which are generated with no interaction between Prover and Refuter, and online certificates, which are based on such an interaction, and are thus shorter. We show that our approach is useful also for certification of separability of regular languages by a DFA of a given size. Unlike DFA minimization, which can be solved in polynomial time, separation is NP-complete, and thus the certification approach is essential. In addition, we prove NP-completeness of a strict version of separation.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::55c3aa82ea6cf4ec3fcc20b1c73225d8 https://doi.org/10.1007/978-3-030-88885-5_4 Zobrazit plný text záznamu