Detail výsledku

Generalized One-Sided Forbidding Grammars

MEDUNA, A.; ZEMEK, P. Generalized One-Sided Forbidding Grammars. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2013, vol. 90, no. 2, p. 172-182. ISSN: 0020-7160.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Zemek Petr, Ing., Ph.D., FIT (FIT), UIFS (FIT)
Abstrakt

In generalized one-sided forbidding grammars (GOFGs), each context-free rule has associated a finite set of forbidding strings, and the set of rules is divided into the sets of left and right forbidding rules. A left forbidding rule can rewrite a nonterminal if each of its forbidding strings is absent to the left of the rewritten symbol. A right forbidding rule is applied analogically. Apart from this, they work like any generalized forbidding grammar. This paper proves the following three results. (1) GOFGs where each forbidding string consists of at most two symbols characterize the family of recursively enumerable languages. (2) GOFGs where the rules in one of the two sets of rules contain only ordinary context-free rules without any forbidding strings characterize the family of context-free languages. (3) GOFGs with the set of left forbidding rules coinciding with the set of right forbidding rules characterize the family of context-free languages.

Klíčová slova

formal languages, regulated rewriting, generalized one-sided forbidding grammars, language families, generative power

URL
Rok
2013
Strany
172–182
Časopis
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, roč. 90, č. 2, ISSN 0020-7160
DOI
10.1080/00207160.2012.723703
BibTeX 
@article{BUT103403,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="Generalized One-Sided Forbidding Grammars",
  journal="INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS",
  year="2013",
  volume="90",
  number="2",
  pages="172--182",
  doi="10.1080/00207160.2012.723703",
  issn="0020-7160",
  url="http://www.tandfonline.com/doi/abs/10.1080/00207160.2012.723703"
}
Projekty
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