In this thesis, an algorithm for learning subsequential transducers is presented from two different perspectives: as an extension of Angluin's algorithm for learning deterministic finite automata and as an instantiation of a more generic categorical algorithm valid for a larger class of automata. The adopted categorical approach considers automata as functors from a category representing words to a certain output category. Some sufficient properties for yielding the existence of minimal automata are presented, together with some additional hypotheses relative to termination to ensure the correctness of the generic algorithm. Remarkably, the conditions required in Angluin’s original algorithm and in its extended version for subsequential transducers naturally arise as the generic categorical algorithm is instantiated with the proper output categories.
It is not uncommon to understand facts, processes and results better by looking at them from above: learning is not an exception. Learning is a crucial area in computer science, especially in artificial intelligence: knowing how to deal with communication, mistakes and experience plays an essential role to progress in learning. But even more important is learning what makes communication possible: a language. A language can be initially thought as a subset of a set of words over an alphabet, always supposed to be finite.The relation between languages and automata has become clearer and clearer in the last decades, since Noam Chomsky gave a mathematical model of a grammar in the second half of the last century.
A deterministic finite automaton accepts a language, called regular, and for every regular language there exists a deterministic finite automaton being minimal, i.e. with a minimal number of states, that accepts it. An analogous thing happens for subsequential transducers, which are automata more complex than deterministic finite automata: in this case, some partial functions, called subsequential, from a set of words to another over possibly different alphabets are accepted;asubsequential transducer accepts a particular subsequential function and for every subsequential function there exists a minimal subsequential transducer accepting it. This is the reason why learning regular languages and subsequential functions may be pursued by learning the minimal automata accepting them.
Inhaltsverzeichnis (Table of Contents)
- Abstract
- Introduction
- I Learning automata from queries and counterexamples
- 1 Angluin's learning algorithm
- 1.1 Deterministic finite automata
- 1.2 Minimal deterministic finite automata
- 1.3 Hypothesis deterministic finite automata
- 1.4 Angluin's algorithm for DFA
- 1.5 Efficiency of Angluin's algorithm for DFA
- 1.6 A running DFA example
- 2 Learning subsequential transducers
- 2.1 Subsequential transducers
- 2.2 Mathematical background for subsequential transducers
- 2.3 Minimal subsequential transducers
- 2.4 Hypothesis subsequential transducers
- 2.5 The learning algorithm for SST . .
- 2.6 Correctness and termination of the learning algorithm for SST
- 2.7 Efficiency of the learning algorithm for SST
- 2.8 A running SST example
- 1 Angluin's learning algorithm
- II Learning automata from a categorical perspective
- 3 A categorical approach for minimizing automata
- 3.1 Factorization systems
- 3.2 Languages and automata as functors
- 3.3 Minimization of automata
- 4 A categorical approach for learning automata
- 4.1 Hypothesis automata .
- 4.2 The basic categorical learning algorithm
- 4.3 The optimized categorical learning algorithm
- 5 Learning subsequential transducers categorically
- 5.1 A category for subsequential transducers.
- 5.2 Initial and final subsequential transducers
- 5.3 Minimality and noetherianity for SST
- 5.4 The learning algorithm for SST from the categorical algorithm
- 3 A categorical approach for minimizing automata
- Conclusion
- Acknowledgements
- Ringraziamenti
- Bibliography
Zielsetzung und Themenschwerpunkte (Objectives and Key Themes)
This thesis aims to present a comprehensive approach to learning subsequential transducers, a type of finite-state machine. It explores this concept through two perspectives: as an extension of Angluin's algorithm for learning deterministic finite automata, and as an instantiation of a broader categorical approach. The research emphasizes the importance of applying category theory to the field of automata learning, demonstrating its effectiveness in simplifying and generalizing the learning process.- Learning subsequential transducers through Angluin's algorithm and a categorical framework.
- Extending Angluin's algorithm for deterministic finite automata to handle subsequential transducers.
- Exploring the utilization of category theory in automata learning, emphasizing its potential for simplification and generalization.
- Developing and analyzing the categorical FunL*-algorithm for a larger class of automata.
- Investigating the properties of minimal automata within a categorical framework.
Zusammenfassung der Kapitel (Chapter Summaries)
- Chapter 1: Introduces Angluin's algorithm for learning deterministic finite automata, a foundational concept for the thesis. It explains the fundamental principles of the algorithm and its efficiency, illustrating them through examples.
- Chapter 2: Focuses on learning subsequential transducers, a more complex type of automaton. It introduces the theoretical foundation of subsequential transducers, detailing their structure and properties. The chapter then presents a learning algorithm specifically designed for subsequential transducers, discussing its correctness, termination, and efficiency.
- Chapter 3: Presents a categorical perspective on minimizing automata, employing the concept of factorization systems. It explores how automata can be viewed as functors in a categorical framework, leading to a more generalized understanding of minimization processes.
- Chapter 4: Extends the categorical framework to the problem of learning automata. This chapter outlines the basic categorical learning algorithm and its optimized counterpart, highlighting the potential for a more unified and generalized approach to learning automata.
- Chapter 5: Applies the categorical learning algorithm to the specific case of learning subsequential transducers. It introduces a category specifically for subsequential transducers and demonstrates how the categorical algorithm can be effectively used to learn these automata.
Schlüsselwörter (Keywords)
Subsequential transducers, Angluin's algorithm, deterministic finite automata, categorical approach, FunL*-algorithm, factorization systems, automata learning, minimization of automata, category theory.- Quote paper
- Riccardo Stabile (Author), 2024, Learning Subsequential Transducers. A Categorical Approach, Munich, GRIN Verlag, https://www.grin.com/document/1467389
