Počet záznamů: 1

Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences

SYSNO ASEP	0362865
Druh ASEP	C - Konferenční příspěvek (mezinárodní konf.)
Zařazení RIV	D - Článek ve sborníku
Název	Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences
Tvůrce(i)	Wiedermann, Jiří (UIVT-O)_{RID, SAI, ORCID}
Zdroj.dok.	Description Complexity of Formal Systems. - Berlin : Springer, 2011 / Holzer M. ; Kutrib M. ; Pighizzini G. - ISSN 0302-9743 - ISBN 978-3-642-22599-4
Rozsah stran	s. 314-327
Poč.str.	14 s.
Akce	DCFS 2011. International Workshop on Descriptional Complexity of Formal Systems /13./
Datum konání	25.07.2011-27.07.2011
Místo konání	Giessen
Země	DE - Německo
Typ akce	WRD
Jazyk dok.	eng - angličtina
Země vyd.	DE - Německo
Klíč. slova	multitape computations ; crossing sequences ; nondeterministic simulation
Vědní obor RIV	IN - Informatika
CEP	GAP202/10/1333 GA ČR - Grantová agentura ČR
CEZ	AV0Z10300504 - UIVT-O (2005-2011)
EID SCOPUS	79961191016
DOI	10.1007/978-3-642-22600-7_25
Anotace	Developing the concept of crossing sequences for multitape computations proposed in 1979 by G. Wechsung, we derive new relations among complexity measures for nondeterministic multitape computations. Especially, we characterize inherent relations between nondeterministic time and space and other complexity measures related to the notion of crossing sequences. We also show a nondeterministic simulation of nondeterministic computations whose complexity depends on the length of crossing sequences of the simulated machine. To a certain extent our results mirror classical results known to hold for single-tape computations or for deterministic multitape computations.
Pracoviště	Ústav informatiky
Kontakt	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Rok sběru	2012

Počet záznamů: 1