About: Generalized One-Sided Forbidding Grammars

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

About: Generalized One-Sided Forbidding Grammars Goto Sponge Distinct 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.tandfonline.com/doi/abs/10.1080/00207160.2012.723703
Description	In generalized one-sided forbidding grammars (GOFGs), each context-free rule has associated a finite set of forbidding strings, and the set of rules is divided into the sets of left and right forbidding rules. A left forbidding rule can rewrite a nonterminal if each of its forbidding strings is absent to the left of the rewritten symbol. A right forbidding rule is applied analogically. Apart from this, they work like any generalized forbidding grammar. This paper proves the following three results. (1) GOFGs where each forbidding string consists of at most two symbols characterize the family of recursively enumerable languages. (2) GOFGs where the rules in one of the two sets of rules contain only ordinary context-free rules without any forbidding strings characterize the family of context-free languages. (3) GOFGs with the set of left forbidding rules coinciding with the set of right forbidding rules characterize the family of context-free languages. In generalized one-sided forbidding grammars (GOFGs), each context-free rule has associated a finite set of forbidding strings, and the set of rules is divided into the sets of left and right forbidding rules. A left forbidding rule can rewrite a nonterminal if each of its forbidding strings is absent to the left of the rewritten symbol. A right forbidding rule is applied analogically. Apart from this, they work like any generalized forbidding grammar. This paper proves the following three results. (1) GOFGs where each forbidding string consists of at most two symbols characterize the family of recursively enumerable languages. (2) GOFGs where the rules in one of the two sets of rules contain only ordinary context-free rules without any forbidding strings characterize the family of context-free languages. (3) GOFGs with the set of left forbidding rules coinciding with the set of right forbidding rules characterize the family of context-free languages. (en)
Title	Generalized One-Sided Forbidding Grammars Generalized One-Sided Forbidding Grammars (en)
skos:prefLabel	Generalized One-Sided Forbidding Grammars Generalized One-Sided Forbidding Grammars (en)
skos:notation	RIV/00216305:26230/13:PU106273!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	2
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	76316
http://linked.open...ai/riv/idVysledku	RIV/00216305:26230/13:PU106273
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	formal languages, regulated rewriting, generalized one-sided forbidding grammars, language families, generative power (en)
http://linked.open.../riv/klicoveSlovo	generative power language families formal languages regulated rewriting generalized one-sided forbidding grammars
http://linked.open...odStatuVydavatele	GB - Spojené království Velké Británie a Severního Irska
http://linked.open...ontrolniKodProRIV	[54BC996C1B2D]
http://linked.open...i/riv/nazevZdroje	International Journal of Computer Mathematics
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	90
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	0020-7160
number of pages	11 (xsd:int)
http://bibframe.org/vocab/doi	10.1080/00207160.2012.723703
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, 112 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software