Detail publikace

Descriptional Complexity of Generalized Forbidding Grammars

MEDUNA Alexander a ŠVEC Martin. Descriptional Complexity of Generalized Forbidding Grammars. International Journal of Computer Mathematics, roč. 2003, č. 80, s. 11-17. ISSN 0020-7160.
Název česky
Složitost popisu gramatik s rozptýleným kontextem
Typ
článek v časopise
Jazyk
angličtina
Autoři
Klíčová slova

Složitost popisu, gramatiky s rozptýleným kontextem

Abstrakt

Složitost popisu gramatik s rozptýleným kontextem je zkoumána.

Anotace

Tento článek diskutuje popisnou složitost zobecněných zakazujících gramatik. Dokazuje, že každý rekurzivně spočetný jazyk je generován zobecněnou gramatikou obsahující nejvýše třináct zakazujících pravidel a nejvýše patnáct neterminálů.

Rok
2003
Strany
11-17
Časopis
International Journal of Computer Mathematics, roč. 2003, č. 80, ISSN 0020-7160
Kniha
International Journal of Computer Mathematics
Vydavatel
Taylor & Francis Informa plc
Místo
London, GB
BibTeX
@ARTICLE{FITPUB7034,
   author = "Alexander Meduna and Martin \v{S}vec",
   title = "Descriptional Complexity of Generalized Forbidding Grammars",
   pages = "11--17",
   booktitle = "International Journal of Computer Mathematics",
   journal = "International Journal of Computer Mathematics",
   volume = 2003,
   number = 80,
   year = 2003,
   location = "London, GB",
   publisher = "Taylor \& Francis Informa plc",
   ISSN = "0020-7160",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7034"
}
Nahoru