Počet záznamů: 1
Simple restriction in context-free rewriting
- 1.
SYSNO ASEP 0346739 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Simple restriction in context-free rewriting Tvůrce(i) Masopust, Tomáš (MU-W) RID, ORCID, SAI Zdroj.dok. Journal of Computer and System Sciences. - : Elsevier - ISSN 0022-0000
Roč. 76, č. 8 (2010), s. 837-846Poč.str. 10 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova formal languages ; context-free grammar ; rewriting system ; derivation restriction ; generative power Vědní obor RIV BA - Obecná matematika CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000281501900010 EID SCOPUS 81955165104 DOI 10.1016/j.jcss.2010.04.001 Anotace Many rewriting systems with context-free productions and with controlled derivations have been studied. On one hand, these systems preserve the simplicity of applications of context-free productions and, on the other hand, they increase the generative power to cover more aspects of natural and programming languages. However, with λ-productions, many of these systems are computationally complete. It gives rise to a natural question of what are the simplest restrictions of the derivation process of context-free grammars to obtain the universal power. In this paper, we present such a simple restriction introducing so-called restricted context-free rewriting systems. These systems are context-free grammars with a function assigning a nonterminal coupled with + or − to each nonterminal. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2011
Počet záznamů: 1