Publication result detail

Scattered Context in Formal Languages

TECHET, J.

Original Title

Scattered Context in Formal Languages

English Title

Scattered Context in Formal Languages

Type

Dissertation

Original Abstract

The present thesis studies theoretical properties of scattered context grammars. The research is focused on four main areas. First, it examines the conditions under which erasing productions can be removed form a scattered context grammar. Second, four modifications of scattered context grammars are introduced and studied. Specifically, the considered modifications involve scattered context grammars with non-context-free components, derivations limited to the first n nonterminals, leftmost derivations, and, finally, derivations in which either the maximal or the minimal number of nonterminals is rewritten in every derivation step. Next, the thesis studies generators of sentences in which every sentence is enriched with a sequence of productions used during its generation. Canonical and reduced generators of this kind are discussed. Finally, several applications of scattered context grammars to natural language description and processing are presented.

English abstract

The present thesis studies theoretical properties of scattered context grammars. The research is focused on four main areas. First, it examines the conditions under which erasing productions can be removed form a scattered context grammar. Second, four modifications of scattered context grammars are introduced and studied. Specifically, the considered modifications involve scattered context grammars with non-context-free components, derivations limited to the first n nonterminals, leftmost derivations, and, finally, derivations in which either the maximal or the minimal number of nonterminals is rewritten in every derivation step. Next, the thesis studies generators of sentences in which every sentence is enriched with a sequence of productions used during its generation. Canonical and reduced generators of this kind are discussed. Finally, several applications of scattered context grammars to natural language description and processing are presented.

Keywords

formal language theory, scattered context grammars, generative power, descriptional complexity, erasing productions, canonical derivations, linguistics

Key words in English

formal language theory, scattered context grammars, generative power, descriptional complexity, erasing productions, canonical derivations, linguistics

Authors

TECHET, J.

Released

10.03.2008

Publisher

Faculty of Information Technology BUT

Location

Brno

Pages count

123

BibTex

@misc{BUT67032,
  author="Jiří {Techet}",
  title="Scattered Context in Formal Languages",
  year="2008",
  pages="123",
  publisher="Faculty of Information Technology BUT",
  address="Brno"
}