Number of the records: 1

Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences

SYSNO ASEP	0362865
Document Type	C - Proceedings Paper (int. conf.)
R&D Document Type	Conference Paper
Title	Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences
Author(s)	Wiedermann, Jiří (UIVT-O)_{RID, SAI, ORCID}
Source Title	Description Complexity of Formal Systems. - Berlin : Springer, 2011 / Holzer M. ; Kutrib M. ; Pighizzini G. - ISSN 0302-9743 - ISBN 978-3-642-22599-4
Pages	s. 314-327
Number of pages	14 s.
Action	DCFS 2011. International Workshop on Descriptional Complexity of Formal Systems /13./
Event date	25.07.2011-27.07.2011
VEvent location	Giessen
Country	DE - Germany
Event type	WRD
Language	eng - English
Country	DE - Germany
Keywords	multitape computations ; crossing sequences ; nondeterministic simulation
Subject RIV	IN - Informatics, Computer Science
R&D Projects	GAP202/10/1333 GA ČR - Czech Science Foundation (CSF)
CEZ	AV0Z10300504 - UIVT-O (2005-2011)
EID SCOPUS	79961191016
DOI	10.1007/978-3-642-22600-7_25
Annotation	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.
Workplace	Institute of Computer Science
Contact	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Year of Publishing	2012

Number of the records: 1