Volume 345; Issue 2-3

Theoretical Computer Science

Volume 345; Issue 2-3
1

Preface

V. Koubek, J. Kratochvíl
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 44 KB
english, 2005
2

A hierarchy of shift equivalent sofic shifts

Marie-Pierre Béal, Francesca Fiorenzi, Dominique Perrin
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 206 KB
english, 2005
4

A new dimension sensitive property for cellular automata

Vincent Bernardi, Bruno Durand, Enrico Formenti, Jarkko Kari
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 157 KB
english, 2005
5

The enumerability of P collapses P to NC

Alina Beygelzimer, Mitsunori Ogihara
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 148 KB
english, 2005
6

Generation problems

E. Böhler, C. Glaßer, B. Schwarz, K.W. Wagner
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 328 KB
english, 2005
7

The non-parametrizability of the word equation : A short proof

Elena Czeizler
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 115 KB
english, 2005
8

A generalization of repetition threshold

Lucian Ilie, Pascal Ochem, Jeffrey Shallit
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 292 KB
english, 2005
9

Resource bounded symmetry of information revisited

Troy Lee, Andrei Romashchenko
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 196 KB
english, 2005
10

The complexity of equivalence and isomorphism of systems of equations over finite groups

Gustav Nordh
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 192 KB
english, 2005
11

Sublogarithmic ambiguity

Klaus Wich
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 311 KB
english, 2005
12

Universal test for quantum one-way permutations

Akinori Kawachi, Hirotada Kobayashi, Takeshi Koshiba, Raymond H. Putra
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 182 KB
english, 2005
13

Author index

Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 150 KB
english, 2005
14

One query reducibilities between partial information classes

Sebastian Bab, Arfst Nickelsen
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 205 KB
english, 2005
15

Decidability of trajectory-based equations

Michael Domaratzki, Kai Salomaa
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 288 KB
english, 2005
16

Graph exploration by a finite automaton

Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, David Peleg
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 181 KB
english, 2005
17

All superlinear inverse schemes are coNP-hard

Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 156 KB
english, 2005
18

A reducibility for the dot-depth hierarchy

Victor L. Selivanov, Klaus W. Wagner
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 250 KB
english, 2005
19

The dual of concatenation

Alexander Okhotin
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 315 KB
english, 2005