betaFeedback

WorksComputer Science

Complete Test Suites for Effectful Automata

Abstract

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.

2012 ACM Subject Classification Theory of computation → Formalisms; Theory of computation → Quantitative automata

Keywords and phrases Automata, conformance testing, categorical methods, weighted automata

Digital Object Identifier 10.4230/LIPIcs...

Funding This research is supported by the NWO grant No. VI.Vidi.223.096.

Acknowledgements We want to thank Henning Urbat and Fabian Lenke for discussions about join-semilattices, tensor products, and join-irreducible elements. We are also very grateful to the anonymous reviewers for their time and useful comments, which improved the paper.

Introduction

The W-method is a celebrated result in conformance testing of deterministic finite state machines (FSMs) by Chow [16] and Vasilevskii [61]. The W-method generates a finite test suite based on a specification FSM. Crucially, this test suite is complete, meaning that any (black-box) implementation that passes the test suite and has no more states than the specification is necessarily behaviourally equivalent. Behavioural equivalence is a strong property: it means that the two systems give equal outputs on any of the infinitely many inputs. On top of that, the test suite generated by the W-method is only polynomial in size.

One area where conformance testing is used is active automata learning. Algorithms such as L* [4] and its descendants assume access to an equivalence oracle, that is, a way of deciding whether a hypothesis is correct with respect to the system under learning (SUL). In active automata learning, the SUL is typically assumed to be black-box. A common way to realise the equivalence oracle is through conformance testing, where the hypothesis is viewed as the specification and the SUL as the implementation. Libraries such as LearnLib [22] and AALpy [48] have implemented the W-method and its extensions.

Active automata learning has been generalised to various types of automata, such as non-deterministic automata [13], weighted automata [11], stochastic systems with observable non-determinism [58], and many others, including categorical frameworks that generalise and extend some of these algorithms [9, 59, 30, 17, 7]. This motivates us to also extend the W-method to a broader class of automata, since these algorithms all rely on equivalence queries. In particular, the main challenge that we address in this paper is to develop a framework for the W-method and its completeness that applies to types of automata beyond deterministic ones, such as non-deterministic automata and weighted automata.

The aim of constructing test suites for non-deterministic FSMs is not new. Petrenko and Yevtushenko describe a complete test suite in [52] with many references to prior work; we discuss more related work in § 7. In this line of research, the fault domain, i.e. the class of models for which the test suite is complete, is fixed: it is the class of automata of a certain size. Our aim instead is to generalise the W-method specifically without fixing our fault domain a priori. This idea of taking a more liberal fault domain follows [39] and is strongly connected to the notion of kk-AA-completeness by Vaandrager and Melse [60].

To this end, we build on the generalised W-method developed in [39] at the level of automata in monoidal closed categories, which includes instances such as deterministic automata, Mealy and Moore machines, and deterministic nominal automata [12]. Weighted automata over a field are also described in [39], but the examples there require additional analysis beyond what the framework offers, and a systematic theory is missing. In particular, non-deterministic automata and weighted automata over Z\mathbb{Z} are not covered in op. cit.

Our approach is to develop a categorical framework for conformance testing based on effectful automata, i.e. automata that have an effectful transition structure modelled using a monad. Formally, these are automata in the Kleisli category of a monad, as already studied by Arbib and Manes [6], and they naturally cover automata with non-deterministic, weighted, or stochastic transition structure. To obtain a general framework, we aim to instantiate the theory in [39]. However, this leads to a technical challenge: the assumptions are not met for automata in Kleisli categories, as these categories do not have enough structure to construct the test suites required by the W-method. Therefore, we exploit the algebraic structure of effectful automata by working in Eilenberg-Moore categories of commutative monads (§ 4). Showing that the framework applies to these categories is non-trivial, and it is one of the main contributions of this paper.

Based on this development, we reach our key contributions: the notions of effectful state cover and effectful state characteriser that are used to construct the effectful W-method (§ 5). We derive the completeness of the effectful W-method from the general theory. Furthermore, we illustrate the effectful W-method by deriving complete test suites for non-deterministic automata and weighted automata over the ring Z\mathbb{Z} (§ 6).

We assume familiarity with basic category theory, such as categories, functors, natural transformations, limits, colimits, adjunctions, and monads. These notions are covered by standard textbooks (e.g. [43, 3, 8, 54]). We also rely heavily on symmetric monoidal closed categories and some further categorical notions, which are recalled in Appendix § 9.

Automata in categories

We recall the basics of automata in a category (see e.g. [5, 2, 24]). Throughout the paper, we fix a base category CC, a functor F ⁣:C→CF \colon C \to C, an initial state object II, and an output object OO.

Definition 2.1. An FF-automaton in CC consists of a state space Q∈CQ \in C, a transition morphism δ ⁣:FQ→Q\delta\colon FQ \to Q, an input morphism i ⁣:I→Qi \colon I \to Q, and an output morphism o ⁣:Q→Oo \colon Q \to O.

If the functor FF is clear from context, we simply use the term automaton.

Example 2.2. Let C\mathcal{C} be the category Set of sets and functions, let FF be defined as FA:=A×ΣFA := A \times\Sigma for some finite alphabet Σ\Sigma, let II be the singleton set 1:={∗}1 := \{\ast\}, and let OO be the two-element set 2:={0,1}2 := \{0,1\}. Then an FF-automaton is given by a set of states QQ, a transition function δ:Q×Σ→Q\delta: Q \times\Sigma\to Q, an initial state i:1→Qi : 1 \to Q, and an acceptance condition o:Q→2o : Q \to2. Thus, an FF-automaton with a finite state space is a deterministic finite automaton (DFA) [53].

Example 2.3. The previous example can be generalised by replacing the base category Set with an arbitrary monoidal category (C,⊗,1)(\mathcal{C}, \otimes, 1) (see Definition A.1). For such a category C\mathcal{C} and any alphabet object Σ∈C\Sigma\in\mathcal{C}, we can set FA:=A⊗ΣFA := A \otimes\Sigma. Letting I:=1I := 1 while leaving the output object OO arbitrary, we obtain the notion of sequential automata as defined by Adámek and Trnková [2], also called machines by Goguen [24]. This notion encompasses many instances such as weighted automata [56], semilattice automata [49], and nominal automata [12].

The transition morphism of an FF-automaton is an algebra for the functor FF. In general, an FF-algebra (or simply algebra) is a pair (A,a)(A,a) with A∈CA \in\mathcal{C} and a:FA→Aa : FA \to A. An FF-algebra homomorphism f:(A,a)→(B,b)f : (A,a) \to(B,b) is a map f:A→Bf : A \to B such that f∘a=b∘Fff \circ a = b \circ Ff. Together, these form a category Alg⁡(F)\operatorname{Alg}(F). Moreover, the notion of algebra homomorphism extends to automata. A homomorphism of FF-automata from (Q1,δ1,i1,o1)(Q_1,\delta_1,i_1,o_1) to (Q2,δ2,i2,o2)(Q_2,\delta_2,i_2,o_2) is an FF-algebra map f:(Q1,δ1)→(Q2,δ2)f : (Q_1,\delta_1) \to(Q_2,\delta_2) such that f∘i1=i2f \circ i_1 = i_2 and o2∘f=o1o_2 \circ f = o_1. FF-automata and their homomorphisms form a category Aut⁡O(F)\operatorname{Aut}_{O}(F).

Given an object A∈CA \in\mathcal{C}, a free FF-algebra over AA consists of an object F∗A∈CF^{\ast}A \in\mathcal{C} and morphisms ζA:FF∗A→F∗A\zeta_A : FF^{\ast}A \to F^{\ast}A and ηA:A→F∗A\eta_A : A \to F^{\ast}A such that for every B∈CB \in\mathcal{C}, b:FB→Bb : FB \to B, and f:A→Bf : A \to B, there exists a unique FF-algebra morphism f~:(F∗A,ζA)→(B,b)\tilde{f} : (F^{\ast}A,\zeta_A) \to(B,b) with f~∘ηA=f\tilde{f} \circ\eta_A = f. We refer to f~\tilde{f} as the free FF-extension of ff. For an algebra (A,a)(A,a), we write a∗a^{\ast} for 1A:(F∗A,ζA)→(A,a)1_A : (F^{\ast}A,\zeta_A) \to(A,a). If free FF-algebras exist over all objects of C\mathcal{C}, we say that FF is a varietor [2]. If C\mathcal{C} has and FF preserves colimits of ω\omega-chains, then FF is a varietor [1, 35].

In the context of automata theory, F∗IF^{\ast}I generalises the set of words: it is an object describing all possible inputs to an automaton. This motivates the following definitions.

Definition 2.4. Let FF be a varietor, and A=(Q,δ,i,o)\mathcal{A} = (Q,\delta,i,o) an FF-automaton.

  • A behaviour (or language) is a morphism F∗I→OF^{\ast}I \to O.

  • The reachability map rA:F∗I→Qr_{\mathcal{A}} : F^{\ast}I \to Q of A\mathcal{A} is the free FF-extension of the input morphism ii.

  • The behaviour BA:F∗I→OB_{\mathcal{A}} : F^{\ast}I \to O of A\mathcal{A} is the composite F∗I→rAQ→oOF^{\ast}I \xrightarrow{r_{\mathcal{A}}} Q \xrightarrow{o} O.

Intuitively, the reachability map sends an input word to the state reached after processing that word. The behaviour, then, is defined by observing the output of the corresponding state.

Example 2.5. The functor FF corresponding to DFAs (Example 2.2) is a varietor, and F∗1F^{\ast}1 is isomorphic to Σ∗\Sigma^{\ast}, the set of words over Σ\Sigma. Therefore, a behaviour Σ∗→2\Sigma^{\ast} \to2 is precisely a language in the classical sense, i.e. a set of words.

The reachability and behaviour maps in Definition 2.4 instantiate to the standard notions in the case of DFAs. Recall that, for a given DFA (Q,δ,q0,Γ)(Q,\delta,q_0,\Gamma), the generalised transition function δ∗:Q×Σ∗→Q\delta^{\ast} : Q \times\Sigma^{\ast} \to Q is defined inductively by δ∗(q,ε):=q\delta^{\ast}(q,\varepsilon) := q and δ∗(q,va):=δ(δ∗(q,v),a)\delta^{\ast}(q,va) := \delta(\delta^{\ast}(q,v),a). Then the reachability map is rA(v)=δ∗(q0,v)r_{\mathcal{A}}(v) = \delta^{\ast}(q_0,v), and the behaviour coincides with the usual accepted language of A\mathcal{A}: BA(v)=1B_{\mathcal{A}}(v) = 1 iff rA(v)∈Γr_{\mathcal{A}}(v) \in\Gamma.

An important automata-theoretic notion that is missing from Definition 2.4 is the observability map. For a DFA (Q,δ,q0,Γ)(Q,\delta,q_0,\Gamma), the observability map μA:Q→2Σ∗\mu_{\mathcal{A}} : Q \to2^{\Sigma^{\ast}} sends a state q∈Qq \in Q to the accepted language of qq, defined as LA(q):={v∈Σ∗∣δ∗(q,v)∈Γ}\mathcal{L}_{\mathcal{A}}(q) := \{v \in\Sigma^{\ast} \mid\delta^{\ast}(q,v) \in\Gamma\}.

To define this generally, we use a categorical analogue of the set of languages 2Σ∗2^{\Sigma^{\ast}}. We assume that our base category C\mathcal{C} is monoidal closed (Definition A.1); we use the notation [A,B][A,B] for the internal hom. Then we may construct the object [F∗1,O][F^*1,O], thought of as the behaviour object, and define the observability map as a morphism Q→[F∗1,O]Q \to[F^*1,O]. This approach to behaviours was introduced by Goguen [24] in the case of sequential automata (Example 2.3).

To be able to define the observability map this way for an arbitrary functor FF, we need a left strength for F∗F^* (see Definition A.2). If we assume, besides closedness, that C\mathcal{C} is a symmetric monoidal category (Definition A.1), then any left strength σ\sigma for FF induces a canonical left strength σ∗\sigma^* for F∗F^* [44 Proposition 6.7].

References

  1. [1]Jiří Adámek. Free algebras and automata realizations in the language of categories. Commentationes Mathematicae Universitatis Carolinae, 015(4):589–602, 1974. URL: https://dml.cz/handle/10338.dmlcz/105583.
  2. [2]Jiří Adámek and Věra Trnková. Automata and Algebras in Categories, volume 37 of Mathematics and its Applications. Springer Dordrecht, 1990.
  3. [3]Jiří Adámek, Horst Herrlich, and George E. Strecker. Abstract and Concrete Categories: The Joy of Cats. TAC Reprints, 2006. URL: https://tac.mta.ca/tac/reprints/articles/17/tr17abs.html.
  4. [4]Dana Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 75(2):87–106, 1987. doi:10.1016/0890-5401(87)90052-6.
  5. [5]Michael A. Arbib and Ernest G. Manes. Adjoint machines, state-behavior machines, and duality. Journal of Pure and Applied Algebra, 6(3):313–344, 1975. doi:10.1016/0022-4049(75)90028-6.DOI
  6. [6]Michael A. Arbib and Ernest G. Manes. Fuzzy machines in a category. Bulletin of the Australian Mathematical Society, 13(2):169–210, 1975. doi:10.1017/S0004972700024412.DOI
  7. [7]Quentin Aristote and Daniela Petrișan. Learning bottom-up tree automata valued in monoidal categories. In Nathalie Bertrand and Stefan Milius, editors, 29th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2026), volume 16503 of Lecture Notes in Computer Science, pages 21–42, 2026. doi:10.1007/978-3-032-22730-0_2.DOI
  8. [8]Steve Awodey. Category Theory. Oxford Logic Guides. Oxford University Press, 2010.
  9. [9]Simone Barlocco, Clemens Kupke, and Jurriaan Rot. Coalgebra learning via duality. In Mikołaj Bojańczyk and Alex Simpson, editors, 22nd International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2019), volume 11425 of Lecture Notes in Computer Science, pages 62–79, 2019. doi:10.1007/978–3–030–17127–8_4.
  10. [10]Jon Beck. Distributive laws. In H. Appelgate, M. Barr, J. Beck, F. W. Lawvere, F. E. J. Linton, E. Manes, M. Tierney, F. Ulmer, and B. Eckmann, editors, Seminar on Triples and Categorical Homology Theory, volume 80 of Lecture Notes in Mathematics, pages 119–140, 1969. doi:10.1007/BFb0083084.DOI
  11. [11]Francesco Bergadano and Stefano Varricchio. Learning behaviors of automata from multiplicity and equivalence queries. SIAM Journal on Computing, 25(6):1268–1280, 1996. doi:10.1137/S009753979326091X.
  12. [12]Mikołaj Bojańczyk, Bartek Klin, and Sławomir Lasota. Automata with group actions. In 26th Annual Symposium on Logic in Computer Science (LICS 2011), pages 355–364, 2011. doi:10.1109/LICS.2011.48.DOI
  13. [13]Benedikt Bollig, Peter Habermehl, Carsten Kern, and Martin Leucker. Angluin-style learning of NFA. In Craig Boutilier, editor, 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), pages 1004–1009, 2009. URL: https://www.ijcai.org/proceedings/2009/.
  14. [14]Filippo Bonchi, Marcello M. Bonsangue, Michele Boreale, Jan J. M. M. Rutten, and Alexandra Silva. A coalgebraic perspective on linear weighted automata. Information and Computation, 211:77–105, 2012. doi:10.1016/J.IC.2011.12.002.
  15. [15]Petra van den Bos, Ramon Janssen, and Joshua Moerman. n-complete test suites for IOCO. Software Quality Journal, 27(2):563–588, 2019. doi:10.1007/S11219–018–9422–X.
  16. [16]Tsun S. Chow. Testing software design modeled by finite-state machines. IEEE Transactions on Software Engineering, 4(3):178–187, 1978. doi:10.1109/TSE.1978.231496.
  17. [17]Thomas Colcombet, Daniela Petrisan, and Riccardo Stabile. Learning automata and transducers: A categorical approach. In Christel Baier and Jean Goubault-Larrecq, editors, 29th Annual Conference on Computer Science Logic (CSL 2021), volume 183 of Leibniz International Proceedings in Informatics, pages 15:1–15:17, 2021. doi:10.4230/LIPIcs.CSL.2021.15.DOI
  18. [18]Hubert Comon, Max Dauchet, Rémi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison, and Marc Tommasi. Tree automata techniques and applications, 2008. URL: https://inria.hal.science/hal–03367725.
  19. [19]François Denis, Aurélien Lemay, and Alain Terlutte. Residual finite state automata. Fundamenta Informaticae, 51(4):339–368, 2002. doi:10.1007/3–540–44693–1_13.
  20. [20]Manfred Droste, Werner Kuich, and Heiko Vogler, editors. Handbook of Weighted Automata. Monographs in Theoretical Computer Science. An EATCS Series. Springer, 2009. doi:10.1007/978–3–642–01492–5.DOI
  21. [21]Manfred Droste and Dietrich Kuske. Weighted automata. In Jean-Eric Pin, editor, Handbook of Automata Theory, pages 113–150. EMS Press, 2021. doi:10.4171/automata–1/4.DOI
  22. [22]Markus Frohme, Falk Howar, and Bernhard Steffen. LearnLib: 10 years later. In Ruzica Piskac and Zvonimir Rakamarić, editors, 37th International Conference on Computer Aided Verification (CAV 2025), volume 15934 of Lecture Notes in Computer Science, pages 141–160, 2025. doi:10.1007/978–3–031–98685–7_7.
  23. [23]Susumu Fujiwara, Gregor von Bochmann, Ferhat Khendek, Mokhtar Amalou, and Abderrazak Ghedamsi. Test selection based on finite state models. IEEE Transactions on Software Engineering, 17(6):591–603, 1991. doi:10.1109/32.87284.
  24. [24]Joseph A. Goguen. Discrete-time machines in closed monoidal categories I. Journal of Computer and System Sciences, 10(1):1–43, 1975. doi:10.1016/S0022–0000(75)80012–2.
  25. [25]Ichiro Hasuo, Bart Jacobs, and Ana Sokolova. Generic trace semantics via coinduction. Logical Methods in Computer Science, 3(4:11):1–36, 2007. doi:10.2168/LMCS–3(4:11)2007.DOI
  26. [26]Gerco van Heerdt. CALF: Categorical Automata Learning Framework. PhD thesis, University College London, 2020. URL: https://discovery.ucl.ac.uk/id/eprint/10110356/.
  27. [27]Gerco van Heerdt, Tobias Kappé, Jurriaan Rot, Matteo Sammartino, and Alexandra Silva. Tree automata as algebras: Minimisation and determinisation. In Markus Roggenbach and Ana Sokolova, editors, 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019), volume 139 of Leibniz International Proceedings in Informatics, pages 6:1–6:22, 2019. doi:10.4230/LIPIcs.CALCO.2019.6.DOI
  28. [28]Gerco van Heerdt, Tobias Kappé, Jurriaan Rot, Matteo Sammartino, and Alexandra Silva. A categorical framework for learning generalised tree automata. In Helle Hvid Hansen and Fabio Zanasi, editors, 16th International Workshop on Coalgebraic Methods in Computer Science (CMCS 2022), volume 13225 of Lecture Notes in Computer Science, pages 67–87, 2022. doi:10.1007/978-3-031-10736-8_4.DOI
  29. [29]Gerco van Heerdt, Matteo Sammartino, and Alexandra Silva. CALF: Categorical automata learning framework. In Valentin Goranko and Mads Dam, editors, 26th Annual Conference on Computer Science Logic (CSL 2017), volume 82 of Leibniz International Proceedings in Informatics, pages 29:1–29:24, 2017. doi:10.4230/LIPIcs.CSL.2017.29.DOI
  30. [30]Gerco van Heerdt, Matteo Sammartino, and Alexandra Silva. Learning automata with side-effects. In Daniela Petrişan and Jurriaan Rot, editors, 15th International Workshop on Coalgebraic Methods in Computer Science (CMCS 2020), volume 12094 of Lecture Notes in Computer Science, pages 68–89, 2020. doi:10.1007/978-3-030-57201-3_5.DOI
  31. [31]Claudio Hermida and Bart Jacobs. Structural induction and coinduction in a fibrational setting. Information and Computation, 145(2):107–152, 1998. doi:10.1006/inco.1998.2725.DOI
  32. [32]Bart Jacobs, Alexandra Silva, and Andrei Sokola. Trace semantics via determinization. Journal of Computer and System Sciences, 81(5):859–879, 2015. doi:10.1016/j.jcss.2014.12.005.DOI
  33. [33]P. T. Johnstone. Adjoint lifting theorems for categories of algebras. Bulletin of the London Mathematical Society, 7(3):294–297, 1975. doi:10.1112/blms/7.3.294.DOI
  34. [34]Peter T. Johnstone. Sketches of an Elephant: A Topos Theory Compendium, Vol. 1. Oxford University Press, 2002. doi:10.1093/oso/9780198534259.001.0001.
  35. [35]G. Max Kelly. A unified treatment of transfinite constructions for free algebras, free monoids, colimits, associated sheaves, and so on. Bulletin of the Australian Mathematical Society, 22(1):1–83, 1980. doi:10.1017/S0004972700006353.DOI
  36. [36]Anders Kock. Monads on symmetric monoidal closed categories. Archiv der Mathematik, 21(1):1–10, 1970. doi:10.1007/BF01220868.DOI
  37. [37]Anders Kock. Closed categories generated by commutative monads. Journal of the Australian Mathematical Society, 12(4):405–424, 1971. doi:10.1017/S1446788700010272.DOI
  38. [38]Anders Kock. Strong functors and monoidal monads. Archiv der Mathematik, 23(1):113–120, 1972. doi:10.1007/BF01304852.DOI
  39. [39]Bálint Kocsis and Jurriaan Rot. Complete test suites for automata in monoidal closed categories. In Parosh Aziz Abdulla and Delia Kesner, editors, 28th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2025), volume 15691 of Lecture Notes in Computer Science, pages 198–219, 2025. doi:10.1007/978-3-031-90897-2_10.DOI
  40. [40]Loes Kruger, Sebastian Junges, and Jurriaan Rot. Small test suites for active automata learning. In Bernd Finkbeiner and Laura Kovács, editors, 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2024), volume 14571 of Lecture Notes in Computer Science, pages 109–129, 2024. doi:10.1007/978-3-031-57249-4_6.DOI
  41. [41]Fred E. J. Linton. Coequalizers in categories of algebras. In H. Applegate, M. Barr, J. Beck, F. W. Lawvere, F. E. J. Linton, E. Manes, M. Tierney, F. Ulmer, and B. Eckmann, editors, Seminar on Triples and Categorical Homology Theory, volume 80 of Lecture Notes in Mathematics, pages 75–90, 1969. doi:10.1007/BFb0083082.DOI
  42. [42]Timo Maarse. Active Mealy machine learning using action refinements. Master’s thesis, Radboud University Nijmegen, The Netherlands, 2020. URL: https://www.cs.ru.nl/F. Vaandrager/thesis-2019_NWI-IMC048_s4416295.pdf.
  43. [43]Saunders Mac Lane. Categories for the Working Mathematician, volume 5 of Graduate Texts in Mathematics. Springer, 1978. doi:10.1007/978-1-4757-4721-8.DOI
  44. [44]Dylan McDermott and Tarmo Uustalu. What makes a strong monad? Electronic Proceedings in Theoretical Computer Science, 360:113–133, 2022. doi:10.4204/EPTCS.360.6.DOI
  45. [45]Joshua Moerman. Nominal Techniques and Black Box Testing for Automata Learning. PhD thesis, Radboud University, 2019. URL: https://joshuamoerman.nl/thesis/.
  46. [46]Philip S. Mulry. Lifting theorems for Kleisli categories. In Stephen Brookes, Michael Main, Austin Melton, Michael Mislove, and David Schmidt, editors, 9th International Conference on Mathematical Foundations of Programming Semantics (MFPS 1993), volume 802 of Lecture Notes in Computer Science, pages 304–319, 1994. doi:10.1007/3-540-58027-1_15.DOI
  47. [47]Philip S. Mulry. Lifting results for categories of algebras. Theoretical Computer Science, 278(1):257–269, 2002. doi:10.1016/S0304-3975(00)00338-8.DOI
  48. [48]Edi Muskardin, Bernhard K. Aichernig, Ingo Pill, Andrea Pferscher, and Martin Tappler. AALpy: An active automata learning library. Innovations in Systems and Software Engineering, 18(3):417–426, 2022. doi:10.1007/S11334-022-00449-3.DOI
  49. [49]Robert S. R. Myers, Jiří Ádámek, Stefan Milius, and Henning Urbat. Canonical nondeterministic automata. In Marcello M. Bonsangue, editor, 12th International Workshop on Coalgebraic Methods in Computer Science (CMCS 2014), volume 8446 of Lecture Notes in Computer Science, pages 189–210, 2014. doi:10.1007/978-3-662-44124-4_11.DOI
  50. [50]Carl V. Page. Equivalence between probabilistic and deterministic sequential machines. Information and Control, 9(5):469–520, 1966. doi:10.1016/S0019-9958(66)80012-8.DOI
  51. [51]Alexandre Petrenko, Gregor von Bochmann, and Ming Yu Yao. On fault coverage of tests for finite state specifications. Computer Networks and ISDN Systems, 29(1):81–106, 1996. doi:10.1016/S0169-7552(96)00019-0.DOI
  52. [52]Alexandre Petrenko and Nina Yevtushenko. Adaptive testing of nondeterministic systems with FSM. In 15th International Symposium on High-Assurance Systems Engineering (HASE 2014), pages 224–228, 2014. doi:10.1109/HASE.2014.39.DOI
  53. [53]Michael O. Rabin and Dana S. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3(2):114–125, 1959. doi:10.1147/rd.32.0114.DOI
  54. [54]Emily Riehl. Category theory in context. Aurora: Dover modern math originals. Dover Publications, 2016.
  55. [55]Robert Sachtleben. An Approach for the Verification and Synthesis of Complete Test Generation Algorithms for Finite State Machines. PhD thesis, Bremen University, Germany, 2022. doi:10.26092/elib/1665.DOI
  56. [56]Marcel-Paul Schützenberger. On the definition of a family of automata. Information and Control, 4(2-3):245–270, 1961. doi:10.1016/S0019-9958(61)80020-X.DOI
  57. [57]Gavin J. Seal. Tensors, monads and actions. Theory and Applications of Categories, 28(15):403–433, 2013. doi:10.70930/tac/evuevg2.arxiv.org/abs/1205.0101
  58. [58]Martin Tappler, Bernhard K. Aichernig, Giovanni Bacci, Maria Eichlseder, and Kim G. Larsen. L*-based learning of Markov decision processes (extended version). Formal Aspects of Computing, 33(4–5):575–615, 2021. doi:10.1007/S00165-021-00536-5.DOI
  59. [59]Henning Urbat and Lutz Schröder. Automata learning: An algebraic approach. In Holger Hermanns, Lijun Zhang, Naoki Kobayashi, and Dale Miller, editors, 35th Annual Symposium on Logic in Computer Science (LICS 2020), pages 900–914, 2020. doi:10.1145/3373718.3394775.DOI
  60. [60]Frits W. Vaandrager and Ivo Melse. New fault domains for conformance testing of finite state machines. In Patricia Bouyer and Jaco van de Pol, editors, 36th International Conference on Concurrency Theory (CONCUR 2025), volume 348 of Leibniz International Proceedings in Informatics, pages 34:1–34:22, 2025. doi:10.4230/LIPIcs.CONCUR.2025.34.arxiv.org/abs/2410.19405
  61. [61]M. P. Vasilevskii. Failure diagnosis of automata. Cybernetics and Systems Analysis, 9(4):653–665, 1973. doi:10.1007/BF01068590.

Paper details

vlnc:W_68xcjrwh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents