Lehr- und Forschungseinheit für Theoretische Informatik,
Institut für Informatik
der Ludwig-Maximilians-Universität München
Arbeitsgemeinschaft (WS 06/07)
Komplexität und Programmiersprachen
Literatur
-
K. Etessami.
Counting quantifiers, successor relations,
and logarithmic space, 1997
-
Bojanczyk, Colcombet.
TWA do not recognize all regular languages, STOC 2005
-
Cook, Rackoff.
Space lower bounds for maze threadability on restricted machines, 1980
-
Poon.
A space lower bound for st-connectivity on Node-named JAGs,
TCS 2000
-
Edmunds, Poon, Achlioptas.
Tight lower bounds for st-connectivity on the NNJAG model, 1999
-
Edmonds, Barnes.
Time-Space Lower Bounds for Directed st-Connectivity on JAG Models, FOCS 1993
-
Allender, Mix Barrington, Chakraborty, Datta, Roy.
Grid Graph Reachability Problems, 2005
-
Allender, Datta, Roy.
The Directed Planar Reachability Problem, 2005
-
Ajtai, Fagin.
Reachability is harder for directed than for undirected finite graphs, J. Symbolic Logic 55, 1, 1990