@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.},
}