IDLIQ: An Incremental Deterministic Finite Automaton Learning Algorithm Through Inverse Queries for Regular Grammar...

Area of Science:

• Computer Science
• Theoretical Computer Science
• Machine Learning

Background:

• Deterministic Finite Automata (DFA) are fundamental in theoretical computer science and pattern recognition.
• Existing incremental learning algorithms for DFAs can have high time complexity, limiting their application to complex systems.
• The Identification of Regular Languages (ID) algorithm provides a foundation for DFA learning but requires adaptation for incremental settings.

Purpose of the Study:

• To present an efficient incremental learning algorithm for Deterministic Finite Automata (DFA).
• To reduce the time complexity of incremental DFA learning compared to existing methods.
• To ensure convergence to a minimal DFA representation with finite labeled examples.

Main Methods:

• The study introduces the Incremental DFA Learning algorithm through Inverse Queries (IDLIQ).
• This algorithm extends the Identification of Regular Languages (ID) algorithm to an incremental learning setup.
• It utilizes labeled examples, membership queries (MQ), and inverse queries (IQ) posed to a minimally adequate teacher (MAT).

Main Results:

• The IDLIQ algorithm achieves a reduced time complexity (from cubic to square) in the presence of a MAT.
• The algorithm constructs a hypothesis automaton consistent with all observed examples and IQ responses.
• Convergence to a minimal DFA representation is ensured with a finite number of labeled examples.

Conclusions:

• The IDLIQ algorithm offers a more efficient approach to incremental DFA learning.
• The reduced complexity makes it more suitable for learning large and complex systems.
• The correctness and termination of the IDLIQ algorithm have been formally proven.