Publication detail

Derivation in Scattered Context Grammar via Lazy Function Evaluation

JIRÁK, O. KOLÁŘ, D.

Original Title

Derivation in Scattered Context Grammar via Lazy Function Evaluation

English Title

Derivation in Scattered Context Grammar via Lazy Function Evaluation

Type

conference paper

Language

en

Original Abstract

This paper is extension of the article published in the MEMICS'09 conference. This paper discusses scattered context grammars (SCG) and considers the application of scattered context grammar production rules. We use function that represents single derivation step over the given sentential form. Moreover, we define this function in such a way, so that it represents the delayed execution of scattered context grammar production rules using the same principles as a lazy evaluation in functional programming. Finally, we prove equivalence of the usual and the delayed execution of SCG production rules.

English abstract

This paper is extension of the article published in the MEMICS'09 conference. This paper discusses scattered context grammars (SCG) and considers the application of scattered context grammar production rules. We use function that represents single derivation step over the given sentential form. Moreover, we define this function in such a way, so that it represents the delayed execution of scattered context grammar production rules using the same principles as a lazy evaluation in functional programming. Finally, we prove equivalence of the usual and the delayed execution of SCG production rules.

Keywords

scattered context grammars, SCG, delayed execution, lazy evaluation, derivation

RIV year

2009

Released

15.12.2009

Publisher

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Location

Wadern

ISBN

978-3-939897-15-6

Book

Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)

Edition

NEUVEDEN

Edition number

NEUVEDEN

Pages from

1

Pages to

10

Pages count

10

URL

Documents

BibTex


@inproceedings{BUT30915,
  author="Ota {Jirák} and Dušan {Kolář}",
  title="Derivation in Scattered Context Grammar via Lazy Function Evaluation",
  annote="This paper is extension of the article published in the MEMICS'09 conference.
This paper discusses scattered context grammars (SCG) and considers the
application of scattered context grammar production rules. We use function that
represents single derivation step over the given sentential form. Moreover, we
define this function in such a way, so that it represents the delayed execution
of scattered context grammar production rules using the same principles as a lazy
evaluation in functional programming. Finally, we prove equivalence of the usual
and the delayed execution of SCG production rules.",
  address="Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik",
  booktitle="Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)",
  chapter="30915",
  edition="NEUVEDEN",
  howpublished="print",
  institution="Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik",
  number="13",
  year="2009",
  month="december",
  pages="1--10",
  publisher="Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik",
  type="conference paper"
}