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

• WAKATSUKI Mitsuo

  Faculty of Electro-Communications, The University of Electro-Communications The Institute of Electronics, Information and Communication Engineers

• TOMITA Etsuji

  Faculty of Electro-Communications, The University of Electro-Communications The Institute of Electronics, Information and Communication Engineers

Abstract

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 droca's, called Szilard strict droca's, and studies the problem of identifying the subclass in the limit from positive data. The class of languages accepted by Szilard strict droca's coincides with the class of Szilard languages (or, associated languages) of strict droca's 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 droca's, we show that the class of Szilard strict droca's 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.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E91-D (6), 1704-1718, 2008

  The Institute of Electronics, Information and Communication Engineers

Keywords

• identification in the limit from positive data
• characteristic sample
• polynomial time learning
• deterministic restricted one-counter automaton

Details

• CRID: 1390282679355978112
• NII Article ID: 10026804329
• NII Book ID: AA10826272
• DOI: 10.1093/ietisy/e91-d.6.1704
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E91.D/6/E91.D_6_1704/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
• Abstract License Flag: Disallowed