Identification in the Limit of Substitutable Context Free Languages

Alexander Clark; Remi Eyraud

Identification in the Limit of Substitutable Context Free Languages

Alexander Clark, Remi Eyraud

Philosophy

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

17 Citations (Scopus)

Abstract

This paper formalises the idea of substitutability introduced by Zellig Harris in the 1950s and makes it the basis for a learning algorithm from positive data only for a subclass of context-free grammars. We show that there is a polynomial characteristic set, and thus prove polynomial identification in the limit of this class. We discuss the relationship of this class of languages to other common classes discussed in grammatical inference. We also discuss modifications to the algorithm that produces a reduction system rather than a context-free grammar, that will be much more compact. We discuss the relationship to Angluin's notion of reversibility for regular languages.

Original language	Undefined/Unknown
Title of host publication	Proceedings of The 16th International Conference on Algorithmic Learning Theory
Editors	Sanjay Jain, Hans Ulrich Simon, Etsuji Tomita
Publisher	Springer
Pages	283-296
Number of pages	14
Volume	3734 LNAI
Publication status	Published - 2005

Cite this

@inbook{601cfe35ca2a4d48aa498456ec43e1f3,

title = "Identification in the Limit of Substitutable Context Free Languages",

abstract = "This paper formalises the idea of substitutability introduced by Zellig Harris in the 1950s and makes it the basis for a learning algorithm from positive data only for a subclass of context-free grammars. We show that there is a polynomial characteristic set, and thus prove polynomial identification in the limit of this class. We discuss the relationship of this class of languages to other common classes discussed in grammatical inference. We also discuss modifications to the algorithm that produces a reduction system rather than a context-free grammar, that will be much more compact. We discuss the relationship to Angluin's notion of reversibility for regular languages.",

author = "Alexander Clark and Remi Eyraud",

year = "2005",

language = "Undefined/Unknown",

volume = "3734 LNAI",

pages = "283--296",

editor = "Sanjay Jain and Simon, {Hans Ulrich} and Etsuji Tomita",

booktitle = "Proceedings of The 16th International Conference on Algorithmic Learning Theory",

publisher = "Springer",

}

TY - CHAP

T1 - Identification in the Limit of Substitutable Context Free Languages

AU - Clark, Alexander

AU - Eyraud, Remi

PY - 2005

Y1 - 2005

N2 - This paper formalises the idea of substitutability introduced by Zellig Harris in the 1950s and makes it the basis for a learning algorithm from positive data only for a subclass of context-free grammars. We show that there is a polynomial characteristic set, and thus prove polynomial identification in the limit of this class. We discuss the relationship of this class of languages to other common classes discussed in grammatical inference. We also discuss modifications to the algorithm that produces a reduction system rather than a context-free grammar, that will be much more compact. We discuss the relationship to Angluin's notion of reversibility for regular languages.

AB - This paper formalises the idea of substitutability introduced by Zellig Harris in the 1950s and makes it the basis for a learning algorithm from positive data only for a subclass of context-free grammars. We show that there is a polynomial characteristic set, and thus prove polynomial identification in the limit of this class. We discuss the relationship of this class of languages to other common classes discussed in grammatical inference. We also discuss modifications to the algorithm that produces a reduction system rather than a context-free grammar, that will be much more compact. We discuss the relationship to Angluin's notion of reversibility for regular languages.

M3 - Conference paper

VL - 3734 LNAI

SP - 283

EP - 296

BT - Proceedings of The 16th International Conference on Algorithmic Learning Theory

A2 - Jain, Sanjay

A2 - Simon, Hans Ulrich

A2 - Tomita, Etsuji

PB - Springer

ER -