In this talk, we introduce a novel method for active learning of deterministic real-time one-counter automata (DROCA). The existing techniques for learning DROCA rely on observing the behaviour of the DROCA up to exponentially large counter-values. Our algorithm eliminates this need and requires only a polynomial number of queries. Additionally, our method differs from existing techniques as we learn a minimal counter-synchronous DROCA, resulting in much smaller counter-examples on equivalence queries. Learning a minimal counter-synchronous automaton cannot be done in polynomial time unless P = NP, even in the case of visibly one-counter automata. We use a SAT solver to overcome this difficulty. The solver is used to compute a minimal separating DFA from a given set of positive and negative samples. We implemented the proposed learning algorithm and tested it on randomly generated DROCA. Our evaluations show that the proposed method outperforms the existing techniques on the test set.
Short Bio:
Prince Mathew is pursuing his PhD in Theoretical Computer Science under the guidance of Dr. Sreejith A.V. in the School of Mathematics and Computer Science at IIT Goa.
