About: On context-free rewriting with a simple restriction and its computational completeness

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

About: On context-free rewriting with a simple restriction and its computational completeness 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
Description	This paper discusses context-free rewriting systems in which there exist two disjoint finite sets of rules, and a symbol, referred to as a condition of applicability, is attached to each rule in either of these two sets. In one set, a rule with a symbol attached to it is applicable if the attached symbol occurs in the current rewritten string while in the other set, such a rule is applicable if the attached symbol does not occur there. The present paper demonstrates that these rewriting systems are computationally complete. From this main result, the paper derives several consequences and solves several open problems.<br> This paper discusses context-free rewriting systems in which there exist two disjoint finite sets of rules, and a symbol, referred to as a condition of applicability, is attached to each rule in either of these two sets. In one set, a rule with a symbol attached to it is applicable if the attached symbol occurs in the current rewritten string while in the other set, such a rule is applicable if the attached symbol does not occur there. The present paper demonstrates that these rewriting systems are computationally complete. From this main result, the paper derives several consequences and solves several open problems.<br> (en)
Title	On context-free rewriting with a simple restriction and its computational completeness On context-free rewriting with a simple restriction and its computational completeness (en)
skos:prefLabel	On context-free rewriting with a simple restriction and its computational completeness On context-free rewriting with a simple restriction and its computational completeness (en)
skos:notation	RIV/00216305:26230/09:PU82560!RIV10-MSM-26230___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(GA201/07/0005), Z(MSM0021630528)
http://linked.open...iv/cisloPeriodika	2
http://linked.open...vai/riv/dodaniDat	2010
http://linked.open...aciTvurceVysledku	Meduna, Alexandr Masopust, Tomáš
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	331362
http://linked.open...ai/riv/idVysledku	RIV/00216305:26230/09:PU82560
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	formal languages, context-free grammar, context-free rewriting system, derivation restriction, generative power.<br><br> (en)
http://linked.open.../riv/klicoveSlovo	context-free rewriting system generative power.<br><br> derivation restriction formal languages context-free grammar
http://linked.open...odStatuVydavatele	FR - Francouzská republika
http://linked.open...ontrolniKodProRIV	[79B1B4190B1B]
http://linked.open...i/riv/nazevZdroje	RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
http://linked.open...in/vavai/riv/obor	BD
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Multi-information technologies: Theory, models, and methods
http://linked.open...UplatneniVysledku	2009
http://linked.open...v/svazekPeriodika	43
http://linked.open...iv/tvurceVysledku	Masopust, Tomáš Meduna, Alexandr
http://linked.open...n/vavai/riv/zamer	Výzkum informačních technologií z hlediska bezpečnosti
issn	0988-3754
number of pages	14 (xsd:int)
http://localhost/t...ganizacniJednotka	26230
is http://linked.open...avai/riv/vysledek of	On context-free rewriting with a simple restriction and its computational completeness On context-free rewriting with a simple restriction and its computational completeness On context-free rewriting with a simple restriction and its computational completeness On context-free rewriting with a simple restriction and its computational completeness

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