Abstrakt. Vi presenterar en reflexiv taktik för att bestämma ekvationsteorin av Kleene algebras i Coq bevis assistent. Denna taktik bygger på en noggrann implementering av effektiva finita algoritmer, så att den löser tillfälliga ekvationer omedelbart och korrekt skalor till större uttryck. Beslutsförfarandet har visat sig vara korrekt och fullständigt: korrektheten är fastställd v.r.t. Alla modeller genom att formalisera Kozens initialitetsteorem. Ett motexempel returneras när den givna ekvationen inte håller. Korrekturbeviset är utmanande: det innebär både en exakt analys av de underliggande automatiserade algoritmerna och en hel del algebraiskt resonemang. I synnerhet måste vi formalisera teorin om matriser över en Kleene algebra. Vi bygger vidare på det senaste tillägget av förstklassiga typklasser i Coq för att kunna arbeta effektivt med de inblandade algebraiska strukturerna.
I en betydande utveckling har Braibant och Pous REF implementerat en taktik för att lösa ekvationer i Klene algebras genom att implementera effektiva finita automata algoritmer i Coq.
Deciding Kleene Algebras in Coq
{'venue': 'LMCS 8 (1:16) 2012', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}