A New Approach for Active Automata Learning Based on Apartness
Frits Vaandrager, Bharat Garhewal, Jurriaan Rot, Thorsten Wißmann
Abstract
Abstract We present $$L^{\#}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>L</mml:mi> <mml:mo>#</mml:mo> </mml:msup> </mml:math> , a new and simple approach to active automata learning. Instead of focusing on equivalence of observations, like the $$L^{*}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>L</mml:mi> <mml:mrow> <mml:mrow/> <mml:mo>∗</mml:mo> </mml:mrow> </mml:msup> </mml:math> algorithm and its descendants, $$L^{\#}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>L</mml:mi> <mml:mo>#</mml:mo> </mml:msup> </mml:math> takes a different perspective: it tries to establish apartness , a constructive form of inequality. $$L^{\#}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>L</mml:mi> <mml:mo>#</mml:mo> </mml:msup> </mml:math> does not require auxiliary notions such as observation tables or discrimination trees, but operates directly on tree-shaped automata. $$L^{\#}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>L</mml:mi> <mml:mo>#</mml:mo> </mml:msup> </mml:math> 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^{\#}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>L</mml:mi> <mml:mo>#</mml:mo> </mml:msup> </mml:math> in practice. Experiments with a prototype implementation, written in Rust, suggest that $$L^{\#}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>L</mml:mi> <mml:mo>#</mml:mo> </mml:msup> </mml:math> is competitive with existing algorithms.