Learning Deterministic Context Free Grammars: the Omphalos Competition

Alexander Clark

Learning Deterministic Context Free Grammars: the Omphalos Competition

Alexander Clark

Philosophy

Research output: Contribution to journal › Article › peer-review

18 Citations (Scopus)

Abstract

This paper describes the winning entry to the Omphalos context free grammar learning competition. We describe a context-free grammatical inference algorithm operating on positive data only, which integrates an information theoretic constituent likelihood measure together with more traditional heuristics based on substitutability and frequency. The competition is discussed from the perspective of a competitor. We discuss a class of deterministic grammars, the Non-terminally Separated (NTS) grammars, that have a property relied on by our algorithm, and consider the possibilities of extending the algorithm to larger classes of languages.

Original language	Undefined/Unknown
Pages (from-to)	93-110
Number of pages	18
Journal	MACHINE LEARNING
Volume	66
Issue number	1
Publication status	Published - 1 Jan 2007

Cite this

@article{cc4cd4278fe049beac0a94103b718caa,

title = "Learning Deterministic Context Free Grammars: the Omphalos Competition",

abstract = "This paper describes the winning entry to the Omphalos context free grammar learning competition. We describe a context-free grammatical inference algorithm operating on positive data only, which integrates an information theoretic constituent likelihood measure together with more traditional heuristics based on substitutability and frequency. The competition is discussed from the perspective of a competitor. We discuss a class of deterministic grammars, the Non-terminally Separated (NTS) grammars, that have a property relied on by our algorithm, and consider the possibilities of extending the algorithm to larger classes of languages.",

author = "Alexander Clark",

year = "2007",

month = jan,

day = "1",

language = "Undefined/Unknown",

volume = "66",

pages = "93--110",

journal = "MACHINE LEARNING",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

T1 - Learning Deterministic Context Free Grammars: the Omphalos Competition

AU - Clark, Alexander

PY - 2007/1/1

Y1 - 2007/1/1

N2 - This paper describes the winning entry to the Omphalos context free grammar learning competition. We describe a context-free grammatical inference algorithm operating on positive data only, which integrates an information theoretic constituent likelihood measure together with more traditional heuristics based on substitutability and frequency. The competition is discussed from the perspective of a competitor. We discuss a class of deterministic grammars, the Non-terminally Separated (NTS) grammars, that have a property relied on by our algorithm, and consider the possibilities of extending the algorithm to larger classes of languages.

AB - This paper describes the winning entry to the Omphalos context free grammar learning competition. We describe a context-free grammatical inference algorithm operating on positive data only, which integrates an information theoretic constituent likelihood measure together with more traditional heuristics based on substitutability and frequency. The competition is discussed from the perspective of a competitor. We discuss a class of deterministic grammars, the Non-terminally Separated (NTS) grammars, that have a property relied on by our algorithm, and consider the possibilities of extending the algorithm to larger classes of languages.

M3 - Article

VL - 66

SP - 93

EP - 110

JO - MACHINE LEARNING

JF - MACHINE LEARNING

IS - 1

ER -