Context-Free and E0L Derivations over Free Groups

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F07%3APU73552" target="_blank" >RIV/00216305:26230/07:PU73552 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Context-Free and E0L Derivations over Free Groups
Original language description
In the context-free and E0L grammars discussed in this paper, the derivations are introduced over free groups rather than free monoids. It is proved that both grammars with derivations introduced in this way characterize the family of recursively enumerable languages in a very succinct way. Specifically, this characterization is based on the eight-nonterminal contextfree grammars and six-nonterminal E0L grammars over free groups.
Czech name
Bezkontextové a E0L derivace nad volnými grupami
Czech description
V bezkontextových a E0L gramatikách popisovaných v tomto článku jsou derivace zavedeny nad volnými grupami, místo nad volnými monoidy. Je dokázáno, že obě gramatiky s derivacemi zavedenými tímto způsobem popisují třídu rekurzívně vyčíslitelných jazyků. Přesněji je tato charakterizace založena na osmi-nonterminálových bezkontextových gramatikách a šestinonterminálových E0L gramatikách nad volnými grupami.<br>

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
JC - Computer hardware and software
OECD FORD branch
—

Project
<a href="/en/project/GA201%2F07%2F0005" target="_blank" >GA201/07/0005: Multi-information technologies: Theory, models, and methods</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)