A New Approach for Active Automata Learning Based on Apartness
- Open Access
- 2022
- OriginalPaper
- Buchkapitel
- Verfasst von
- Frits Vaandrager
- Bharat Garhewal
- Jurriaan Rot
- Thorsten Wißmann
- Verlag
- Springer International Publishing
Zusammenfassung
We present $$L^{\#}$$ L # , a new and simple approach to active automata learning. Instead of focusing on equivalence of observations, like the $$L^{*}$$ L ∗ algorithm and its descendants, $$L^{\#}$$ L # takes a different perspective: it tries to establish apartness, a constructive form of inequality. $$L^{\#}$$ L # does not require auxiliary notions such as observation tables or discrimination trees, but operates directly on tree-shaped automata. $$L^{\#}$$ L # has the same asymptotic query and symbol complexities as the best existing learning algorithms, but we show that adaptive distinguishing sequences can be naturally integrated to boost the performance of $$L^{\#}$$ L # in practice. Experiments with a prototype implementation, written in Rust, suggest that $$L^{\#}$$ L # is competitive with existing algorithms.
- Titel
- A New Approach for Active Automata Learning Based on Apartness
- Verfasst von
-
Frits Vaandrager
Bharat Garhewal
Jurriaan Rot
Thorsten Wißmann
- Copyright-Jahr
- 2022
- Buch
-
Tools and Algorithms for the Construction and Analysis of Systems
Print ISBN: 978-3-030-99523-2
Electronic ISBN: 978-3-030-99524-9
Copyright-Jahr: 2022
- DOI
- https://doi.org/10.1007/978-3-030-99524-9_12
