← 研踪 PaperTrailarXiv:2611.26535 · v1
Complete Test Suites for Effectful Automata
面向效应自动机的完备测试套件
首次提交 2026-11-20 02:16
版本更新 2026-11-20 02:16
雷达观测 2026-11-20 12:52
摘要
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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-20 02:16 · 最新观测版本
Complete Test Suites for Effectful Automata
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.
查看此版本解读 →查看此版本原文 ↗