Learnability for Restarting Automata
摘要
Restarting automata are a formal model for the linguistic technique of ‘analysis by reduction.’ Accordingly, these automata can be used to study the language-theoretical foundations of this linguistic technique, establishing theoretical results or refuting conjectures. Unfortunately, it is quite a difficult task to design a restarting automaton for a comprehensive language like, e.g., a substantial subset of a natural language.