Theoretical Computer Science

Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures
pp. 1-70(70)
Author: Matz O.

Searching games with errors-fifty years of coping with liars
pp. 71-109(39)
Author: Pelc¹ A.

Some permutation routing algorithms for low-dimensional hypercubes
pp. 111-124(14)
Authors: Hwang F.K.; Yao Y.C.; Dasgupta B.

Inheritance of workflows: an approach to tackling problems related to change
pp. 125-203(79)
Authors: van der Aalst¹ W.M.P.; Basten T.

Calculs sur les structures de langage denombrable
pp. 205-222(18)
Author: Bourgade M.

Restriction categories I: categories of partial maps
pp. 223-259(37)
Authors: Cockett¹ J.R.B.; Lack² S.

The drawability problem for minimum weight triangulations
pp. 261-286(26)
Authors: Lenhart W.; Liotta G.

Control structures in hypothesis spaces: the influence on learning
pp. 287-308(22)
Authors: Case J.; Jain S.; Suraj M.

Deterministic parallel backtrack search
pp. 309-324(16)
Authors: Herley K.T.; Pietracaprina A.; Pucci G.

On-line load balancing of temporary tasks revisited
pp. 325-340(16)
Authors: Lam T.-W.; Ting H.-F.; To K.-K.; Wong W.-H.

On the design of efficient ATM routing schemes
pp. 341-359(19)
Authors: Becchetti L.; Bertolazzi P.; Gaibisso C.; Gambosi G.

Edge coloring of bipartite graphs with constraints
pp. 361-399(39)
Authors: Caragiannis I.; Kaklamanis C.; Persiano P.

Partial words and a theorem of Fine and Wilf revisited
pp. 401-419(19)
Authors: Blanchet-Sadri F.; Hegstrom¹ R.A.

Time-minimal paths amidst moving obstacles in three dimensions
pp. 421-440(20)
Author: Fujimura K.

The stack-size of tries: a combinatorial study
pp. 441-461(21)
Author: Nebel M.E.

Associative language descriptions
pp. 463-491(29)
Authors: Cherubini A.; Crespi Reghizzi¹ S.; San Pietro P.

Decision lists and related Boolean functions
pp. 493-524(32)
Authors: Eiter T.; Ibaraki T.; Makino K.

Asymptotic behavior in a heap model with two pieces
pp. 525-560(36)
Authors: Mairesse J.; Vuillon L.

A priori optimization for the probabilistic maximum independent set problem
pp. 561-590(30)
Authors: Murat C.; Paschos V.T.

Computational complexity of some problems involving congruences on algebras
pp. 591-608(18)
Authors: Bergman C.; Slutzki G.

Decision tree approximations of Boolean functions
pp. 609-623(15)
Authors: Mehta¹ D.; Raghavan² V.

On the complexity of recognizing the Hilbert basis of a linear diophantine system
pp. 625-642(18)
Authors: Durand A.; Hermann M.; Juban L.

Approximating algebraic functions by means of rational ones
pp. 643-657(15)
Authors: Pergola E.; Pinzani R.; Rinaldi S.

On two-sided infinite fixed points of morphisms
pp. 659-675(17)
Authors: Shallit J.; Wang M.-w.

Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time
pp. 677-700(24)
Authors: Kucera¹ A.; Mayr² R.

Operations and language generating devices suggested by the genome evolution
pp. 701-738(38)
Authors: Dassow J.; Mitrana¹ V.; Salomaa A.

Probabilistic rebound Turing machines
pp. 739-760(22)
Authors: Zhang L.; Inoue K.; Ito A.; Wang Y.

Computing LOGCFL certificates
pp. 761-777(17)
Authors: Gottlob G.; Leone N.; Scarcello F.

Membrane systems with carriers
pp. 779-796(18)
Authors: Martn-Vide C.; Paun¹ G.; Rozenberg G.

Constructible functions in cellular automata and their applications to hierarchy results
pp. 797-809(13)
Authors: Iwamoto C.; Hatsuyama T.; Morita K.; Imai K.

Threshold counters with increments and decrements
pp. 811-826(16)
Authors: Busch¹ C.; Demetriou N.; Herlihy M.; Mavronicolas² M.

The structure of a linear chip firing game and related models
pp. 827-841(15)
Authors: Goles E.; Morvan M.; Duong Phan H.

Simple and flexible detection of contiguous repeats using a suffix tree
pp. 843-856(14)
Authors: Stoye¹ J.; Gusfield² D.

The rectangle complexity of functions on two-dimensional lattices
pp. 857-863(7)
Authors: Sander J.W.; Tijdeman R.

The accelerated k-in-a-row game
pp. 865-875(11)
Author: Pluhar A.

Least adaptive optimal search with unreliable tests
pp. 877-893(17)
Authors: Cicalese¹ F.; Mundici² D.; Vaccaro U.

Rush Hour is PSPACE-complete, or ''Why you should generously tip parking lot attendants''
pp. 895-911(17)
Authors: Flake G.W.; Baum E.B.

The Variance of the height of binary search trees
pp. 913-919(7)
Author: Drmota M.

On canonical number systems
pp. 921-933(13)
Authors: Akiyama¹ S.; Petho² A.

Compact factors of countable state Markov shifts
pp. 935-946(12)
Authors: Fiebig D.; Fiebig U.-R.

An example of a computable absolutely normal number
pp. 947-958(12)
Authors: Becher¹ V.; Figueira S.

A pumping lemma for random permitting context languages
pp. 959-967(9)
Authors: Ewert¹ S.; van der Walt² A.

Two undecidability results for chain code picture languages
pp. 969-976(8)
Author: Kim C.

Author index
pp. 977-979(3)

Master index
pp. 981-992(12)