Polynomial Time Identification of Strict Deterministic Restricted One-Counter Automata in Some Class from Positive Data

概要

論文の詳細を見る
A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). When it accepts an input by empty stack, it is called strict. This paper is concerned with a subclass of real-time strict drocas, called Szilard strict drocas, and studies the problem of identifying the subclass in the limit from positive data. The class of languages accepted by Szilard strict drocas coincides with the class of Szilard languages (or, associated languages) of strict drocas and is incomparable to each of the class of regular languages and that of simple languages. After providing some properties of languages accepted by Szilard strict drocas, we show that the class of Szilard strict drocas is polynomial time identifiable in the limit from positive data in the sense of Yokomori. This identifiability is proved by giving an exact characteristic sample of polynomial size for a language accepted by a Szilard strict droca. The class of very simple languages, which is a proper subclass of simple languages, is also proved to be polynomial time identifiable in the limit from positive data by Yokomori, but it is yet unknown whether there exists a characteristic sample of polynomial size for any very simple language.
（社）電子情報通信学会の論文
2008-06-01