ML Anthology

Grammatical Inference on the Basis of Linear Environments of Symbol Strings

Yoshiyuki Kotani
IJCAI 1979 pp. 496-498
/ijcai/1979/kotani1979ijcai-grammatical/

Abstract

A new method of grammatical inference is proposed. The inference procedure, receiving only positive sample sentences, produces a grammar. A notion of is introduced which represents linear environment of a string in sample sentences. The procedure consists of (1) calculating the bounded context of strings, (2) finding a pair of context-equivalent strings, (3) reducing the sample sentences by means of the pair, and (4) iterating (1) to (3) until there is no pair of context-equivalent strings in the reduced sample sentences. The output grammar is constructed from the reduced sentences and the pairs of strings obtained in (2). Sample sentences are grammatically correct with respect to the grammar inferred from the sentences. All of regular languages and a number of non-trivial context-free languages are inferred correctly by the method, when sufficient but a finite number of sample sentences are given.

Semantic Scholar

Cite

Text

Kotani. "Grammatical Inference on the Basis of Linear Environments of Symbol Strings." International Joint Conference on Artificial Intelligence, 1979.

Markdown

[Kotani. "Grammatical Inference on the Basis of Linear Environments of Symbol Strings." International Joint Conference on Artificial Intelligence, 1979.](https://mlanthology.org/ijcai/1979/kotani1979ijcai-grammatical/)

BibTeX

@inproceedings{kotani1979ijcai-grammatical,
  title     = {{Grammatical Inference on the Basis of Linear Environments of Symbol Strings}},
  author    = {Kotani, Yoshiyuki},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {1979},
  pages     = {496-498},
  url       = {https://mlanthology.org/ijcai/1979/kotani1979ijcai-grammatical/}
}