Result Details

Pumping Properties of Path-Restricted Tree-Controlled Languages

KOUTNÝ, J.; KŘIVKA, Z.; MEDUNA, A. Pumping Properties of Path-Restricted Tree-Controlled Languages. 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: Brno University of Technology, 2011. p. 61-69. ISBN: 978-80-214-4305-1.
Type
conference paper
Language
English
Authors
Koutný Jiří, Ing., Ph.D., DIFS (FIT)
Křivka Zbyněk, Ing., Ph.D., DIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Abstract

This paper discusses new kind of a restriction placed on tree-controlled grammars-context-free grammars with some root-to-leaf paths in their derivation trees restricted by a control language. We introduce an n-path restriction and demonstrate that if the control language is linear, there are several families of generated languages depending on the length of common part of restricted paths. Then, the paper introduces several pumping properties of these families.

Keywords
regulated rewriting, 
derivation tree,
tree-controlled grammars,
path-controlled grammars,
$n$-path tree-controlled grammars,
pumping properties.
Published
2011
Pages
61–69
Proceedings
7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Conference
MEMICS'11 -- 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
ISBN
978-80-214-4305-1
Publisher
Brno University of Technology
Place
Brno
BibTeX 
@inproceedings{BUT76416,
  author="Jiří {Koutný} and Zbyněk {Křivka} and Alexandr {Meduna}",
  title="Pumping Properties of Path-Restricted Tree-Controlled Languages",
  booktitle="7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science",
  year="2011",
  pages="61--69",
  publisher="Brno University of Technology",
  address="Brno",
  isbn="978-80-214-4305-1"
}
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
Context-free languages and pushdown automata, MŠMT, KONTAKT, MEB041003, start: 2010-01-01, end: 2011-12-31, completed
Mathematical and Engineering Approaches to Developing Reliable and Secure Concurrent and Distributed Computer Systems, GACR, Doktorské granty, GD102/09/H042, start: 2009-01-30, end: 2012-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