Detail publikačního výsledku

LL Leftmost k-Linear Scattered Context Grammars

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

Originální název

LL Leftmost k-Linear Scattered Context Grammars

Anglický název

LL Leftmost k-Linear Scattered Context Grammars

Druh

Stať ve sborníku mimo WoS a Scopus

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

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

Klíčová slova v angličtině

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

Autoři

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

Rok RIV

2012

Vydáno

21.09.2011

Nakladatel

American Institute of Physics

Místo

Kassandra, Halkidiki

ISBN

978-0-7354-0956-9

Kniha

AIP Conference Proceedings

ISSN

1551-7616

Periodikum

AIP conference proceedings

Svazek

1389

Číslo

1

Stát

Spojené státy americké

Strany od

833

Strany do

836

Strany počet

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"
}