Detail publikace

Computational Completeness Resulting from Scattered Context Grammars Working Under Various Derivation Modes

MEDUNA, A.; SOUKUP, O. Computational Completeness Resulting from Scattered Context Grammars Working Under Various Derivation Modes. Proceedings of MEMICS'14. Brno: NOVPRESS s.r.o., 2014. p. 89-100. ISBN: 978-80-214-5022-6.
Název česky
Výpočetní úplnost gramatik s rozptýleným kontextem vyplývající z jejich práce v různých derivačních módech
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Soukup Ondřej, Ing., Ph.D.
Klíčová slova

scattered context grammars, alternative derivation modes, generative power, computational completeness

Abstrakt

Tento článek představuje a studuje celou škálu derivačních módů gramatik s rozptýleným kontextem. Tyto gramatiky jsou v základu stejné jako klasické gramatiky s rozptýleným kontextem, pouze mohou potenciálně při aplikaci pravidla po vymazání n neterminálu vložit nové podřetězce na jiné pozice, než se nacházeli vymazané neterminály.Článek se zaměřuje na výzkum generativní síly gramatik s rozptýleným kontextem pracujících v těchto derivačních módech. Demonstruje, že jsou ve všech stále výpočetně úplné - tedy stále charakterizují rodinu rekursivně spočetných jazyků.

Rok
2014
Strany
89–100
Sborník
Proceedings of MEMICS'14
Konference
MEMICS'14 -- 9th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Telč, CZ
ISBN
978-80-214-5022-6
Vydavatel
NOVPRESS s.r.o.
Místo
Brno
BibTeX 
@inproceedings{BUT111656,
  author="Alexandr {Meduna} and Ondřej {Soukup}",
  title="Computational Completeness Resulting from Scattered Context Grammars Working Under Various Derivation Modes",
  booktitle="Proceedings of MEMICS'14",
  year="2014",
  pages="89--100",
  publisher="NOVPRESS s.r.o.",
  address="Brno",
  isbn="978-80-214-5022-6",
  url="https://www.fit.vut.cz/research/publication/10730/"
}
Nahoru