Inference of deterministic one-counter languages (Q794442)

This paper presents inference algorithms, for the class of deterministic one-counter languages, that are based on enumeration methods. This method is known as ''identification in the limit''. Such algorithms must generate at least one automaton for each language of the class which recognizes this language. To generate not too many equivalent automata for each language, a method is described that enumerates DOCAs (deterministic one- counter automata) or a certain normal form in such a way that no two isomorphic DOCAs are generated. This is done by the generation of certain partitions on sets of so-called computation traces. This is a generalization of inference methods for finite-state machines. The whole inference method is organized in such a way that all automata are enumerated without final states. The determination of final states is not made till the consistency check with the sample. In the last part of the paper a modification of the above inference is described. This modification results from additional information on computation traces, that is included in the sample.