ML Anthology

Efficient Learning of Real Time Two-Counter Automata (Extended Abstract)

Amr F. Fahmy, Robert S. Roos
ALT 1996 pp. 113-126
doi:10.1007/3-540-61863-5_39 /alt/1996/fahmy1996alt-efficient/

Abstract

This paper describes an efficient algorithm that learns deterministic real time two-counter automata (R2CA) by automata decomposition. R2CA languages properly include ROCA and include languages that are not context free. Let L be an R2CA language and let B , the behavior graph of L , be the reduced infinite automaton that accepts L . The learning algorithm decomposes B_m, an initial finite submachine of B of diameter m , into a complete control structure and a partial 2-counter. Learning happens when the resulting partial 2-counter is replaced with a complete, infinite 2-counter, thus obtaining an infinite behavior from a finite sample. Our decomposition algorithm has complexity O(n^5.5) where n is the number of states of B_m. B_m itself can be constructed using a modification of Angluin's algorithm for learning regular sets.

PDF ALT Semantic Scholar

Cite

Text

Fahmy and Roos. "Efficient Learning of Real Time Two-Counter Automata (Extended Abstract)." International Conference on Algorithmic Learning Theory, 1996. doi:10.1007/3-540-61863-5_39

Markdown

[Fahmy and Roos. "Efficient Learning of Real Time Two-Counter Automata (Extended Abstract)." International Conference on Algorithmic Learning Theory, 1996.](https://mlanthology.org/alt/1996/fahmy1996alt-efficient/) doi:10.1007/3-540-61863-5_39

BibTeX

@inproceedings{fahmy1996alt-efficient,
  title     = {{Efficient Learning of Real Time Two-Counter Automata (Extended Abstract)}},
  author    = {Fahmy, Amr F. and Roos, Robert S.},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {1996},
  pages     = {113-126},
  doi       = {10.1007/3-540-61863-5_39},
  url       = {https://mlanthology.org/alt/1996/fahmy1996alt-efficient/}
}