Detail výsledku

One-Sided Forbidding Grammars and Selective Substitution Grammars

MEDUNA, A.; ZEMEK, P. One-Sided Forbidding Grammars and Selective Substitution Grammars. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2012, vol. 89, no. 5, p. 586-596. ISSN: 0020-7160.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Zemek Petr, Ing., Ph.D., UIFS (FIT)
Abstrakt

In one-sided forbidding grammars, the set of rules is divided into the set of left forbidding rules and the set of right forbidding rules. A left forbidding rule can rewrite a nonterminal if each of its forbidding symbols is absent to the left of the rewritten symbol in the current sentential form while a right forbidding rule is applied analogically except that this absence is verified to the right. Apart from this, they work like ordinary forbidding grammars.

As its main result, the present paper proves that one-sided forbidding grammars are equivalent to selective substitution grammars. This equivalence is established in terms of grammars with and without erasing rules. Furthermore, the paper proves that one-sided forbidding grammars in which the set of left forbidding rules coincides with the set of right forbidding rules characterize the family of context-free languages. In the conclusion, the significance of the achieved results is discussed.

Klíčová slova

Formal language theory, regulated rewriting, one-sided forbidding grammars, selective substitution grammars, generative power

URL
Rok
2012
Strany
586–596
Časopis
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, roč. 89, č. 5, ISSN 0020-7160
DOI
10.1080/00207160.2011.642300
UT WoS
000300852300001
BibTeX 
@article{BUT91446,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="One-Sided Forbidding Grammars and Selective Substitution Grammars",
  journal="INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS",
  year="2012",
  volume="89",
  number="5",
  pages="586--596",
  doi="10.1080/00207160.2011.642300",
  issn="0020-7160",
  url="http://www.tandfonline.com/doi/abs/10.1080/00207160.2011.642300"
}
Projekty
Bezkontextové gramatiky a zásobníkové automaty, MŠMT, KONTAKT, MEB041003, zahájení: 2010-01-01, ukončení: 2011-12-31, ukončen
Centrum excelence IT4Innovations, MŠMT, Operační program Výzkum a vývoj pro inovace, ED1.1.00/02.0070, zahájení: 2011-01-01, ukončení: 2015-12-31, ukončen
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