Detail publikace

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

MASOPUST, T.; MEDUNA, A. On context-free rewriting with a simple restriction and its computational completeness. RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2009, vol. 43, no. 2, p. 365-378. ISSN: 0988-3754.
Název česky
O bezkontextovém přepisování s jednoduchým omezením a jeho výpočetní úplnost
Typ
článek v časopise
Jazyk
anglicky
Autoři
Masopust Tomáš, doc. RNDr., Ph.D. (CK-SZZ)
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
URL
Klíčová slova

formal languages, context-free grammar, context-free rewriting system, derivation restriction, generative power.

Abstrakt

Článek diskutuje bezkontextové přepisovací systémy, v nichž existují dvě konečné disjunktní množiny pravidel, a symbol, označovaný jako podmínka aplikovatelnosti, je přiřazen ke každému pravidlu v obou množinách. V jedné množině jsou pravidla, která jsou aplikovatelná pouze tehdy, pokud se k ním přiřazené symboly vyskytuje ve větné formě, zatímco ve druhé množině jsou pravidla, která jsou aplikovatelná pouze tehdy, pokud se k ním přiřazené symboly nevyskytují ve větné formě. Článek demonstruje, že takovéto přepisující systémy jsou výpočetně úplné. V závěru je pak odvozeno několik důsledků.

Rok
2009
Strany
365–378
Časopis
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, roč. 43, č. 2, ISSN 0988-3754
UT WoS
000264879300012
BibTeX 
@article{BUT49309,
  author="Tomáš {Masopust} and Alexandr {Meduna}",
  title="On context-free rewriting with a simple restriction and its computational completeness",
  journal="RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS",
  year="2009",
  volume="43",
  number="2",
  pages="365--378",
  issn="0988-3754",
  url="http://dx.doi.org/10.1051/ita/2009002"
}
Nahoru