Publication result detail

LL Leftmost k-Linear Scattered Context Grammars

ZEMEK, P.; MEDUNA, A.; VRÁBEL, L.

Original Title

LL Leftmost k-Linear Scattered Context Grammars

English Title

LL Leftmost k-Linear Scattered Context Grammars

Type

Paper in proceedings outside WoS and Scopus

Original Abstract

The present paper introduces a new variant of a scattered context grammar, called an LL leftmost k-linear scattered context grammar. It is an ordinary scattered context grammar without erasing rules, where (1) every scattered context rule is composed of k-linear rules, (2) if we take the first components of every rule, the resulting context-free grammar is an LL grammar, and (3) every rule is applied in a leftmost way. We study the generative power of this variant and its parsing properties, including time and space complexity. In the conclusion, several remarks regarding the achieved results are made.

English abstract

The present paper introduces a new variant of a scattered context grammar, called an LL leftmost k-linear scattered context grammar. It is an ordinary scattered context grammar without erasing rules, where (1) every scattered context rule is composed of k-linear rules, (2) if we take the first components of every rule, the resulting context-free grammar is an LL grammar, and (3) every rule is applied in a leftmost way. We study the generative power of this variant and its parsing properties, including time and space complexity. In the conclusion, several remarks regarding the achieved results are made.

Keywords

Formal languages, scattered context grammars, generative power, parsing, deep pushdown automata

Key words in English

Formal languages, scattered context grammars, generative power, parsing, deep pushdown automata

Authors

ZEMEK, P.; MEDUNA, A.; VRÁBEL, L.

RIV year

2012

Released

21.09.2011

Publisher

American Institute of Physics

Location

Kassandra, Halkidiki

ISBN

978-0-7354-0956-9

Book

AIP Conference Proceedings

ISBN

1551-7616

Periodical

AIP conference proceedings

Volume

1389

Number

1

State

United States of America

Pages from

833

Pages to

836

Pages count

4

URL

http://proceedings.aip.org/resource/2/apcpcs/1389/1/833_1?isAuthorized=no

BibTex

@inproceedings{BUT76321,
  author="Petr {Zemek} and Alexandr {Meduna} and Lukáš {Vrábel}",
  title="LL Leftmost k-Linear Scattered Context Grammars",
  booktitle="AIP Conference Proceedings",
  year="2011",
  journal="AIP conference proceedings",
  volume="1389",
  number="1",
  pages="833--836",
  publisher="American Institute of Physics",
  address="Kassandra, Halkidiki",
  doi="10.1063/1.3636862",
  isbn="978-0-7354-0956-9",
  issn="0094-243X",
  url="http://proceedings.aip.org/resource/2/apcpcs/1389/1/833_1?isAuthorized=no"
}