Number of the records: 1
Simple restriction in context-free rewriting
- 1.
SYSNO ASEP 0346739 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title Simple restriction in context-free rewriting Author(s) Masopust, Tomáš (MU-W) RID, ORCID, SAI Source Title Journal of Computer and System Sciences. - : Elsevier - ISSN 0022-0000
Roč. 76, č. 8 (2010), s. 837-846Number of pages 10 s. Language eng - English Country US - United States Keywords formal languages ; context-free grammar ; rewriting system ; derivation restriction ; generative power Subject RIV BA - General Mathematics CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000281501900010 EID SCOPUS 81955165104 DOI 10.1016/j.jcss.2010.04.001 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2011
Number of the records: 1