Efficient Learning of Real Time One-Counter Automata

Abstract

We present an efficient learning algorithm for languages accepted by deterministic real time one-counter automata (ROCA). The learning algorithm works by first learning an initial segment, B _ n , of the infinite state machine that accepts the unknown language and then decomposing it into a complete control structure and a partial counter. A new, efficient ROCA decomposition algorithm, which will be presented in detail, allows this result. The decomposition algorithm works in time O ( n ^2 log ( n )) where nc is the number of states of B _ n for some language-dependent constant c . If Angluin's algorithm for learning regular languages is used to learn B _ n and the complexity of this step is h(n, m) , where m is the length of the longest counterexample necessary for Angluin's algorithm, the complexity of our algorithm is O(h(n, m) + n ^2 log ( n )).