The search functionality is under construction.
The search functionality is under construction.

Author Search Result

[Author] Yasuhiro TAJIMA(2hit)

1-2hit
  • Teachability of a Subclass of Simple Deterministic Languages

    Yasuhiro TAJIMA  

     
    PAPER-Fundamentals of Information Systems

      Vol:
    E96-D No:12
      Page(s):
    2733-2742

    We show teachability of a subclass of simple deterministic languages. The subclass we define is called stack uniform simple deterministic languages. Teachability is derived by showing the query learning algorithm for this language class. Our learning algorithm uses membership, equivalence and superset queries. Then, it terminates in polynomial time. It is already known that simple deterministic languages are polynomial time query learnable by context-free grammars. In contrast, our algorithm guesses a hypothesis by a stack uniform simple deterministic grammar, thus our result is strict teachability of the subclass of simple deterministic languages. In addition, we discuss parameters of the polynomial for teachability. The “thickness” is an important parameter for parsing and it should be one of parameters to evaluate the time complexity.

  • Polynomial Time Learnability of Simple Deterministic Languages from MAT and a Representative Sample

    Yasuhiro TAJIMA  Etsuji TOMITA  Mitsuo WAKATSUKI  

     
    PAPER-Theory of Automata, Formal Language Theory

      Vol:
    E83-D No:4
      Page(s):
    757-765

    We propose a learning algorithm for simple deterministic languages from queries and a priori knowledge. To the learner, a special finite subset of the target language, called a representative sample, is provided at the beginning and two types of queries, equivalence queries and membership queries, are available. This learning algorithm constructs nonterminals of a hypothesis grammar based on Ishizaka(1990)'s idea. In Ishizaka(1990)'s algorithm, the learner makes rules as many as possible from positive counterexamples, and diagnoses wrong rules from negative counterexamples. In contrast, our algorithm guesses a simple deterministic grammar and diagnoses them using positive and negative counterexamples based on Angluin(1987)'s algorithm.