Result Details

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.
Type
conference paper
Language
English
Authors
Zemek Petr, Ing., Ph.D., DIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Vrábel Lukáš, Ing., DIFS (FIT)
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

URL
Published
2011
Pages
833–836
Journal
AIP Conference Proceedings, vol. 1389, no. 1, ISSN 1551-7616
Proceedings
AIP Conference Proceedings
Conference
9th International Conference of Numerical Analysis and Applied Mathematics
ISBN
978-0-7354-0956-9
Publisher
American Institute of Physics
Place
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",
  url="http://proceedings.aip.org/resource/2/apcpcs/1389/1/833_1?isAuthorized=no"
}
Projects
Advanced recognition and presentation of multimedia data, BUT, Vnitřní projekty VUT, FIT-S-11-2, start: 2011-01-01, end: 2013-12-31, completed
Security-Oriented Research in Information Technology, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, start: 2007-01-01, end: 2013-12-31, running
Research groups
Formal Model Research Group (RG FM)
Departments
Department of Information Systems (DIFS)
Back to top