About: One-Sided Random Context Grammars with Leftmost Derivations

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

About: One-Sided Random Context Grammars with Leftmost Derivations 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://www.springerlink.com/content/mx44705255227153/
Description	In this paper, we study the generative power of one-sided random context grammars working in a leftmost way. More specifically, by analogy with the three well-known types of leftmost derivations in regulated grammars, we introduce three types of leftmost derivations to one-sided random context grammars and prove the following three results. (I) One-sided random context grammars with type-1 leftmost derivations characterize the family of context-free languages. (II) One-sided random context grammars with type-2 and type-3 leftmost derivations characterize the family of recursively enumerable languages. (III) Propagating one-sided random context grammars with type-2 and type-3 leftmost derivations characterize the family of context-sensitive languages. In the conclusion, the generative power of random context grammars and one-sided random context grammars with leftmost derivations is compared. In this paper, we study the generative power of one-sided random context grammars working in a leftmost way. More specifically, by analogy with the three well-known types of leftmost derivations in regulated grammars, we introduce three types of leftmost derivations to one-sided random context grammars and prove the following three results. (I) One-sided random context grammars with type-1 leftmost derivations characterize the family of context-free languages. (II) One-sided random context grammars with type-2 and type-3 leftmost derivations characterize the family of recursively enumerable languages. (III) Propagating one-sided random context grammars with type-2 and type-3 leftmost derivations characterize the family of context-sensitive languages. In the conclusion, the generative power of random context grammars and one-sided random context grammars with leftmost derivations is compared. (en)
Title	One-Sided Random Context Grammars with Leftmost Derivations One-Sided Random Context Grammars with Leftmost Derivations (en)
skos:prefLabel	One-Sided Random Context Grammars with Leftmost Derivations One-Sided Random Context Grammars with Leftmost Derivations (en)
skos:notation	RIV/00216305:26230/12:PU101747!RIV13-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...vai/riv/dodaniDat	2013
http://linked.open...aciTvurceVysledku	Zemek, Petr Meduna, Alexandr
http://linked.open.../riv/druhVysledku	C - Kapitola v knize
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	156537
http://linked.open...ai/riv/idVysledku	RIV/00216305:26230/12:PU101747
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	formal languages, regulated rewriting, one-sided random context grammars, leftmost derivations, generative power (en)
http://linked.open.../riv/klicoveSlovo	generative power formal languages regulated rewriting leftmost derivations one-sided random context grammars
http://linked.open...ontrolniKodProRIV	[7EB5C758D227]
http://linked.open...i/riv/mistoVydani	Berlin-Heidelberg
http://linked.open...vEdiceCisloSvazku	NEUVEDEN
http://linked.open...i/riv/nazevZdroje	LNCS Festschrift Series: Languages Alive - Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...v/pocetStranKnihy	292 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	IT4Innovations Centre of Excellence
http://linked.open...UplatneniVysledku	2012
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
number of pages	14 (xsd:int)
http://bibframe.org/vocab/doi	10.1007/978-3-642-31644-9_11
http://purl.org/ne...btex#hasPublisher	Springer-Verlag
https://schema.org/isbn	978-3-642-31643-2
http://localhost/t...ganizacniJednotka	26230
is http://linked.open...avai/riv/vysledek of	One-Sided Random Context Grammars with Leftmost Derivations

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, 112 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software