Detail výsledku

LL Leftmost k-Linear Scattered Context Grammars

ZEMEK, P.; MEDUNA, A.; VRÁBEL, L. LL Leftmost k-Linear Scattered Context Grammars. AIP Conference Proceedings. AIP conference proceedings. Kassandra, Halkidiki: American Institute of Physics, 2011. no. 1, p. 833-836. ISBN: 978-0-7354-0956-9. ISSN: 1551-7616.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Zemek Petr, Ing., Ph.D., UIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Vrábel Lukáš, Ing., UIFS (FIT)
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

URL
Rok
2011
Strany
833–836
Časopis
AIP conference proceedings, roč. 1389, č. 1, ISSN 1551-7616
Sborník
AIP Conference Proceedings
Konference
9th International Conference of Numerical Analysis and Applied Mathematics
ISBN
978-0-7354-0956-9
Vydavatel
American Institute of Physics
Místo
Kassandra, Halkidiki
DOI
10.1063/1.3636862
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"
}
Projekty
Pokročilé rozpoznávání a prezentace multimediálních dat, VUT, Vnitřní projekty VUT, FIT-S-11-2, zahájení: 2011-01-01, ukončení: 2013-12-31, ukončen
Výzkum informačních technologií z hlediska bezpečnosti, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, zahájení: 2007-01-01, ukončení: 2013-12-31, řešení
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru