Inferring a System from Examples with Time Passage

Abstract

We consider inferring a system from examples with time passage, which we will call an observation. A complete observation is a possibly infinite sequence ( p _0, p _1,..., p _n, ...) of examples, where the ( n +1)-st example p _n of the sequence is chosen nondeterministically from possible candidates that may depend on the time n and the former examples p _0, p _1 ... , p _ n -1. We call the set of all possible complete observations a phenomenon. A phenomenon we introduce is turned out to be a generalization of a formal language as well as a function. We propose a system that generates a phenomenon and discuss inferability in the limit, finite inferability and refutable inferability of systems from their observations. First, we give some characterization theorems on inferability. We also consider inferability from presentations with some additional informations. Finally, we propose phenomena generated by finite automata and discuss their inferability.