Publication detail

Scattered Context Grammars with Priority

KŘOUSTEK, J. ŽIDEK, S. KOLÁŘ, D. MEDUNA, A.

Original Title

Scattered Context Grammars with Priority

English Title

Scattered Context Grammars with Priority

Type

journal article - other

Language

en

Original Abstract

The scattered context grammars are based on application of n context-free productions in parallel to generate their sentences. We can find two basic versions of this grammar type - erasing and propagating grammars. Erasing productions are allowed in erasing grammar, while they are prohibited in propagating grammars. In this paper, we present regulated versions of these grammars, where productions are regulated by the production-priority function. The priority function guarantees that productions will be applied whenever it is possible according to their priority. We also provide formal proofs of generative power of these grammars.

English abstract

The scattered context grammars are based on application of n context-free productions in parallel to generate their sentences. We can find two basic versions of this grammar type - erasing and propagating grammars. Erasing productions are allowed in erasing grammar, while they are prohibited in propagating grammars. In this paper, we present regulated versions of these grammars, where productions are regulated by the production-priority function. The priority function guarantees that productions will be applied whenever it is possible according to their priority. We also provide formal proofs of generative power of these grammars.

Keywords

scattered context grammar, regulation, priority, generative power

RIV year

2011

Released

15.08.2011

Publisher

NEUVEDEN

Location

NEUVEDEN

Pages from

1

Pages to

6

Pages count

6

Documents

BibTex


@article{BUT76359,
  author="Jakub {Křoustek} and Stanislav {Židek} and Dušan {Kolář} and Alexandr {Meduna}",
  title="Scattered Context Grammars with Priority",
  annote="The scattered context grammars are based on application of n context-free
productions in parallel to generate their sentences. We can find two basic
versions of this grammar type - erasing and propagating grammars. Erasing
productions are allowed in erasing grammar, while they are prohibited in
propagating grammars. In this paper, we present regulated versions of these
grammars, where productions are regulated by the production-priority function.
The priority function guarantees that productions will be applied whenever it is
possible according to their priority. We also provide formal proofs of generative
power of these grammars.",
  address="NEUVEDEN",
  chapter="76359",
  edition="NEUVEDEN",
  howpublished="online",
  institution="NEUVEDEN",
  number="4",
  volume="2",
  year="2011",
  month="august",
  pages="1--6",
  publisher="NEUVEDEN",
  type="journal article - other"
}