In their previous paper, Mukouchi and Arikawa discussed both refutability and inferability of a hypothesis space from examples.
If a target language is a member of the hypothesis space, then an inference machine should identify it in the limit, otherwise
it should refute the hypothesis space itself in a finite time. They pointed out the necessity of refutability of a hypothesis
space from a view point of machine discovery. Recently,Mukouchi focused sequences of examples successively generated by a
certain kind of system. He call such a sequence an
observation with time passage, and a sequence extended as long as possible a
complete observation. Then the set of all possible complete observations is called a
phenomenon of the system
In this paper, we introduce phenomena generated by rewriting systems known as 0L systems and pure grammars, and investigate their inferability in the limit from positive examples as well as refutable inferability
from complete examples
First, we show that any phenomenon class generated by 0L systems is inferable in the limit from positive examples. We also
show that the phenomenon class generated by pure grammars such that left hand side of each production is not longer than a
fixed length is inferable in the limit from positive examples, while the phenomenon class of unrestricted pure grammars is
shown not to be inferable. We also obtain the result that the phenomenon class of pure grammars such that the number of productions
and that of axioms are not greater than a fixed number is inferable in the limit from positive examples as well as refutably
inferable from complete examples
Supported in part by Grant-in-Aid for Scientific Research on Priority Areas No. 10143104 from the Ministry of Education, Science
and Culture, Japan.