@Techreport{C12tech,
AUTHOR = {Peter {\v C}erno},
TITLE = {Clearing Restarting Automata and Grammatical Inference},
INSTITUTION = {Charles University, Faculty of Mathematics and Physics},
YEAR = {2012},
NUMBER = {1/2012},
ADDRESS = {Prague},
URL = {http://popelka.ms.mff.cuni.cz/cerno/files/cerno_clra_and_gi.pdf},
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.},
KEYWORDS = {grammatical inference, clearing restarting automata,
subword-clearing restarting automata, formal languages},
}