@INPROCEEDINGS{C12,
author = {Peter {\v C}erno},
affiliation = {Department of Computer Science, Charles University, Faculty of Mathematics and Physics, Malostransk{\'e} n{\'a}m. 25, 118 00 PRAHA 1, Czech Republic},
title = {Clearing Restarting Automata and Grammatical Inference},
booktitle = {Proceedings of the Eleventh International Conference on Grammatical Inference},
series = {JMLR Workshop and Conference Proceedings},
editor = {Jeffrey Heinz, Colin de la Higuera, Tim Oates },
pages = {54--68},
volume = {21},
year = {2012},
abstract = {Clearing and subword-clearing restarting automata are linguistically motivated
models of automata. We investigate the problem of grammatical inference for such
automata based on the given set of positive and negative samples.
We show that it is possible to identify these models in the limit. In this
way we can learn a large class of languages. On the other hand, we prove that
the task of finding a clearing restarting automaton consistent with a
given set of positive and negative samples is NP-hard, provided that we
impose an upper bound on the width of its instructions.},
}