4
$\begingroup$

I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) that necessitates ( n-1 ) equivalence queries for the L* algorithm to correctly learn the automaton.

The L* algorithm operates by building an observation table and using membership and equivalence queries to fill out and correct this table. In each round, the algorithm proposes a hypothesis automaton based on the current observation table. If the hypothesis is incorrect, an equivalence query will provide a counterexample, which is then used to update the table for the next round.

I have been able to construct such DFAs manually for small ( n ) (up to 7), with each automaton requiring one less round than the number of states to be learned. However, I'm struggling to generalize this construction for arbitrary ( n ). Here is the progression pattern I've observed for my DFAs so far (also the observation table for the last hypothesis):

I am looking for a systematic method to create such DFAs for any given ( n ), ensuring the L* algorithm requires ( n-1 ) rounds to learn the DFA. How can this be achieved? Is there a general pattern or formula that can be applied to construct these DFAs?


The approach that I have used so far is brute force, i.e. always changing the state that is furthest away, and then assigning it to a new state and then randomly testing the possible transition for the new states until one more learning round is added

s d a ss qqq aa

aaaa

$\endgroup$
3
  • $\begingroup$ Is your question about how to lower the complexity of the algorithm from the one established by Angluin in the original paper where she describes the algorithm (polynomial but cubic in the number of guesses)? $\endgroup$
    – Chaos
    Feb 20 at 19:56
  • $\begingroup$ @Chaos I'm not familiar with the topic at all but if my English understanding is correct, it appears it asks about creating test cases that perform the absolute worst under the algorithm. @ Everyone Notice this question was bountied for 100 reps by someone else, received 4 votes and no answer. $\endgroup$ Mar 9 at 10:15
  • $\begingroup$ The topic is important and has many practical applications, that is why everyone is eager to hear about how to make the algorithm work efficiently, I still do not understand your question. $\endgroup$
    – Chaos
    Mar 9 at 14:31

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.