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, Bn, 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 O(n2log(n)) where nc is the number of states of Bn for some constant c. If Angluin's algorithm for learning regular languages is used to learn Bn and the complexity of this step is h(n, m) where m is the length of the longest counter example necessary for Angluin's algorithm, the complexity of our algorithm is thus O(h(n, m) + n2log(n)).