Počet záznamů: 1
Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences
- 1.0362865 - ÚI 2012 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Wiedermann, Jiří
Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences.
Description Complexity of Formal Systems. Berlin: Springer, 2011 - (Holzer, M.; Kutrib, M.; Pighizzini, G.), s. 314-327. Lecture Notes in Computer Science, 6808. ISBN 978-3-642-22599-4. ISSN 0302-9743.
[DCFS 2011. International Workshop on Descriptional Complexity of Formal Systems /13./. Giessen (DE), 25.07.2011-27.07.2011]
Grant CEP: GA ČR GAP202/10/1333
Výzkumný záměr: CEZ:AV0Z10300504
Klíčová slova: multitape computations * crossing sequences * nondeterministic simulation
Kód oboru RIV: IN - Informatika
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.
Trvalý link: http://hdl.handle.net/11104/0199046
Název souboru Staženo Velikost Komentář Verze Přístup a0362865.pdf 0 279.2 KB Vydavatelský postprint vyžádat
Počet záznamů: 1