面向效应自动机的完备测试套件
Complete Test Suites for Effectful Automata
Bálint Kocsis, Rick Koenders, Joshua Moerman, Jurriaan Rot
AI 速读 基于摘要
作者基于W-方法的范畴推广,提出一个针对由交换单子定义的效应自动机构造与分析完备测试套件的通用框架,并给出完备性定理。
cs.FL
查看原文摘要
Complete test suites for automata are (finite) sets of words that enable testing an implementation against a specification: when a (black-box) automaton passes the test suite, completeness guarantees that it is equivalent to the specification on all (infinitely many) words. A well-known method for constructing complete test suites for deterministic automata is the W-method, used in conformance testing and automata learning. Based on a recent categorical generalisation of the W-method, we propose a framework for~the construction and analysis of test suites for a certain class of effectful automata defined by commutative monads. By working in the Eilenberg-Moore category of the associated monad at hand, we obtain a generic notion of effectful W-method, together with a completeness theorem. We show how to apply the framework and derive complete test suites for non-deterministic and weighted automata.