About: Left Random Context ET0L Grammars

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Left Random Context ET0L Grammars Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://iospress.metapress.com/content/b3h6456215g6754p/?p=e7359885e380461c96f9663f43ae8b09&pi=2
Description	Consider ET0L grammars. Modify them such that a set of permitting symbols and a set of forbidding symbols are attached to each of their rules, just like in random context grammars. A rule like this can rewrite a symbol if each of its permitting symbols occurs to the left of the symbol to be rewritten in the current sentential form while each of its forbidding symbols does not occur there. ET0L grammars modified in this way are referred to as left random context ET0L grammars, and they represent the principal subject of the investigation in this paper. We prove that these grammars characterize the family of recursively enumerable languages, and without erasing rules, they characterize the family of context-sensitive languages. We also introduce a variety of special cases of these grammars and establish their generative power. In the conclusion, we put all the achieved results into the context of formal language theory as a whole and formulate several open questions. Consider ET0L grammars. Modify them such that a set of permitting symbols and a set of forbidding symbols are attached to each of their rules, just like in random context grammars. A rule like this can rewrite a symbol if each of its permitting symbols occurs to the left of the symbol to be rewritten in the current sentential form while each of its forbidding symbols does not occur there. ET0L grammars modified in this way are referred to as left random context ET0L grammars, and they represent the principal subject of the investigation in this paper. We prove that these grammars characterize the family of recursively enumerable languages, and without erasing rules, they characterize the family of context-sensitive languages. We also introduce a variety of special cases of these grammars and establish their generative power. In the conclusion, we put all the achieved results into the context of formal language theory as a whole and formulate several open questions. (en)
Title	Left Random Context ET0L Grammars Left Random Context ET0L Grammars (en)
skos:prefLabel	Left Random Context ET0L Grammars Left Random Context ET0L Grammars (en)
skos:notation	RIV/00216305:26230/13:PU106272!RIV14-MSM-26230___
http://linked.open...avai/predkladatel	Fakulta informačních technologií
http://linked.open...avai/riv/aktivita	P S Z
http://linked.open...avai/riv/aktivity	P(ED1.1.00/02.0070), S, Z(MSM0021630528)
http://linked.open...iv/cisloPeriodika	3
http://linked.open...vai/riv/dodaniDat	2014
http://linked.open...aciTvurceVysledku	Zemek, Petr Meduna, Alexandr
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Vysoké učení technické v Brně / Fakulta informačních technologií
http://linked.open...dnocenehoVysledku	84611
http://linked.open...ai/riv/idVysledku	RIV/00216305:26230/13:PU106272
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Regulated rewriting, ET0L grammars, random context, left variants, generative power, language families (en)
http://linked.open.../riv/klicoveSlovo	generative power Regulated rewriting language families ET0L grammars left variants random context
http://linked.open...odStatuVydavatele	NL - Nizozemsko
http://linked.open...ontrolniKodProRIV	[D346D9F5C15B]
http://linked.open...i/riv/nazevZdroje	Fundamenta Informaticae
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	IT4Innovations Centre of Excellence
http://linked.open...UplatneniVysledku	2013
http://linked.open...v/svazekPeriodika	123
http://linked.open...iv/tvurceVysledku	Meduna, Alexandr Zemek, Petr
http://linked.open...n/vavai/riv/zamer	Výzkum informačních technologií z hlediska bezpečnosti
issn	0169-2968
number of pages	16 (xsd:int)
http://bibframe.org/vocab/doi	10.3233/FI-2013-811
http://localhost/t...ganizacniJednotka	26230

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software