**BEFMRWW00**-
A. Bouajjani, J. Esparza, A. Finkel, O. Maler, P. Rossmanith, B. Willems, and
P. Wolper.

An efficient automata approach to some problems on context-free grammars.*Information Processing Letters*, 74(5-6):221-227, 2000. [gzipped Postscript ] [Abstract] **BJLR91**-
G. Buntrock, B. Jenner, K.-J. Lange, and P. Rossmanith.

Unambiguity and fewness for logarithmic space.

In L. Budach, editor,*Proceedings of the 8th Conference on Foundations of Computation Theory*, number 529 in Lecture Notes in Computer Science, pages 168-179, Gosen, Fed. Rep. of Germany, September 1991. Springer-Verlag. [dvi ] [gzipped Postscript ] [Abstract] **DHLR93**-
C. Damm, M. Holzer, K.-J. Lange, and P. Rossmanith.

On the very low complexity of deterministic 0L languages.

In G. Rozenberg and A. Salomaa, editors,*Proceedings of Developments in Language Theory: At The Crossroads of Mathematics, Computer Science and Biology*, Turku, Finland, July 1993. World Scientific. [dvi ] [gzipped Postscript ] **DHR94**-
C. Damm, M. Holzer, and P. Rossmanith.

Expressing uniformity via oracles.

In J. Dassow and A. Kelemenova, editors,*Developments in Theoretical Computer Science: Proceedings of the International Meeting of Young Computer Scientists*. Gordon and Breach Science Publishers, 1994. [dvi ] [gzipped Postscript ] [Abstract] **DHR95**-
C. Damm, M. Holzer, and P. Rossmanith.

Expressing uniformity via oracles.

Technical Report 95-01, Universität Trier, Fachbereich IV-Informatik und Mathematik, 54286 Trier, Fed. Rep. of Germany, January 1995. [compressed Postscript ] [Abstract] **DHR97**-
C. Damm, M. Holzer, and P. Rossmanith.

Expressing uniformity via oracles.*Theory of Computer Systems*, 30:355-366, 1997. [compressed Postscript ] [Abstract] **ERSSZ96**-
T. Erlebach, P. Rossmanith, H. Stadtherr, A. Steger, and T. Zeugmann.

Efficient learning of one-variable pattern languages from positive examples.

DOI Technical Report DOI-TR-128, Department of Informatics, Kyushu University, December 1996. [compressed Postscript ] **ERSSZ97**-
T. Erlebach, P. Rossmanith, H. Stadtherr, A. Steger, and T. Zeugmann.

Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries.

In M. Li and A. Maruoka, editors,*Proceedings of the 8th International Workshop on Algorithmic Learning Theory*, number 1316 in Lecture Notes in Computer Science, pages 260-276. Springer-Verlag, October 1997. [dvi ] [gzipped Postscript ] **ERSSZ01**-
T. Erlebach, P. Rossmanith, H. Stadtherr, A. Steger, and T. Zeugmann.

Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries.*Theoretical Computer Science*, 261:119-156, 2001. [gzipped Postscript ] [Abstract] **EHRS00a**-
J. Esparza, D. Hansel, P. Rossmanith, and S. Schwoon.

Efficient algorithms for model checking pushdown systems.

Technical Report TUM-I0002, SFB-Bericht 342/1/00 A, Technische Universität München, Institut für Informatik, February 2000. [gzipped Postscript ] [Abstract] **EHRS00b**-
J. Esparza, D. Hansel, P. Rossmanith, and S. Schwoon.

Efficient algorithms for model checking pushdown systems.

In*Proc. of CAV'2000*, number 1855 in Lecture Notes in Computer Science, pages 232-247. Springer-Verlag, 2000. [gzipped Postscript ] [Abstract] **ER97**-
J. Esparza and P. Rossmanith.

An automata approach to some problems on context-free grammars.

In R. Valk C. Freksa, M. Jantzen, editor,*Foundations of Computer Science, Potential - Theory - Cognition*, number 1337 in Lecture Notes in Computer Science, pages 143-152, 1997. [gzipped Postscript ] [Abstract] **ERS00**-
J. Esparza, P. Rossmanith, and S. Schwoon.

A uniform framework for problems on context-free grammars.*EATCS Bulletin*, 72:169-177, October 2000. [gzipped Postscript ] **GHNR00**-
J. Gramm, E. A. Hirsch, R. Niedermeier, and P. Rossmanith.

New worst-case upper bounds for MAX-2-SAT with applications to MAX-CUT.

Technical Report TR00-037, ECCC, May 2000. [gzipped Postscript ] [Abstract] **GNR01**-
J. Gramm, R. Niedermeier, and P. Rossmanith.

Exact solutions for closest string and related problems.

In*Proceedings of the 12th International Symposium on Algorithms and Computation*, Lecture Notes in Computer Science. Springer-Verlag, 2001.

To appear. **HR96**-
M. Holzer and P. Rossmanith.

A simpler grammar for Fibonacci numbers.*The Fibonacci Quarterly*, 34(5):465-466, November 1996. [compressed Postscript ] **KNRR95**-
M. Kunde, R. Niedermeier, K. Reinhardt, and P. Rossmanith.

Optimal average case sorting on arrays.

In E. W. Mayr and C. Puech, editors,*Proceedings of the 12th Symposium on Theoretical Aspects of Computer Science*, number 900 in Lecture Notes in Computer Science, pages 503-514. Springer-Verlag, 1995. [dvi ] [gzipped Postscript ] **KNRR96**-
M. Kunde, R. Niedermeier, K. Reinhardt, and P. Rossmanith.

Optimal deterministic sorting and routing on grids and tori with diagonals.

Technical Report TUM-I9629, Technische Universität München, Institut für Informatik, July 1996. [compressed Postscript ] **KNRR99**-
M. Kunde, R. Niedermeier, K. Reinhardt, and P. Rossmanith.

Optimal deterministic sorting and routing on grids and tori with diagonals.*Algorithmica*, (25):438-458, 1999. [gzipped Postscript ] [Abstract] **KNR93**-
M. Kunde, R. Niedermeier, and P. Rossmanith.

Faster sorting and routing on grids with diagonals.

Technical Report TUM-I9313, SFB-Bericht Nr. 342/5/93 A, Institut für Informatik, Technische Universität München, June 1993. [compressed Postscript ] **KNR94**-
M. Kunde, R. Niedermeier, and P. Rossmanith.

Faster sorting and routing on grids with diagonals.

In P. Enjalbert, E. W. Mayr, and K. W. Wagner, editors,*Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science*, number 775 in Lecture Notes in Computer Science, pages 225-236. Springer-Verlag, 1994. [compressed Postscript ] **LR90a**-
K.-J. Lange and P. Rossmanith.

Characterizing unambiguous augmented pushdown automata by circuits.

In B. Rovan, editor,*Proceedings of the 15th Conference on Mathematical Foundations of Computer Science*, number 452 in Lecture Notes in Computer Science, pages 399-406, Banská Bystrica, Czechoslovakia, August 1990. Springer-Verlag. [dvi ] [gzipped Postscript ] [Abstract] **LR90b**-
K.-J. Lange and P. Rossmanith.
*Two Results on Unambiguous Circuits*.

SFB-Bericht 342/3/90A, I9006, Institut für Informatik, Technische Universität München, 1990. **LR92**-
K.-J. Lange and P. Rossmanith.

The emptiness problem for intersections of regular languages.

In I. Havel, editor,*Proceedings of the 17th Conference on Mathematical Foundations of Computer Science*, number 629 in Lecture Notes in Computer Science, pages 346-354, Prague, Czechoslavakia, August 1992. Springer-Verlag. [dvi ] [gzipped Postscript ] [Abstract] **LR94a**-
K.-J. Lange and P. Rossmanith.

Unambiguous polynomial hierarchies and exponential size.

In*Proceedings of the 9th IEEE Symposium on Structure in Complexity*, pages 106-115, 1994. [dvi ] [gzipped Postscript ] **LRR92**-
K.-J. Lange, P. Rossmanith, and W. Rytter.

Parallel recognition and ranking of context-free languages.

In I. Havel, editor,*Proceedings of the 17th Conference on Mathematical Foundations of Computer Science*, number 629 in Lecture Notes in Computer Science, pages 24-36, Prague, Czechoslavakia, August 1992. Springer-Verlag. **NR90b**-
R. Niedermeier and P. Rossmanith.
*Unambiguous Simulations of Auxiliary Pushdown Automata and Circuits*.

SFB-Bericht 342/31/90A, I9054, Institut für Informatik, Technische Universität München, December 1990. **NR92c**-
R. Niedermeier and P. Rossmanith.

On the power of reading and writing simultaneously in parallel computations.

Submitted for publication, November 1992. **NR92b**-
R. Niedermeier and P. Rossmanith.

Optimal parallel algorithms for computing recursively defined functions.

Technical Report TUM-I9218, SFB-Bericht Nr. 342/12/92 A, Technische Universität München, June 1992. **NR92a**-
R. Niedermeier and P. Rossmanith.

Unambiguous simulations of auxiliary pushdown automata and circuits.

In I. Simon, editor,*Proceedings of the 1st Symposium on Latin American Theoretical Informatics*, number 583 in Lecture Notes in Computer Science, pages 387-400, São Paulo, Brazil, April 1992. Springer-Verlag. [compressed Postscript ] [Abstract] **NR93a**-
R. Niedermeier and P. Rossmanith.

Extended locally definable acceptance types.

In P. Enjalbert, A. Finkel, and K. W. Wagner, editors,*Proceedings of the 10th Symposium on Theoretical Aspects of Computer Science*, number 665 in Lecture Notes in Computer Science, pages 473-483. Springer-Verlag, 1993. [dvi ] [gzipped Postscript ] **NR93b**-
R. Niedermeier and P. Rossmanith.

On the power of reading and writing simultaneously in parallel computations.

In K. W. Ng, P. Raghavan, N. V. Balasubramanian, and F. Y. L. Chin, editors,*Proceedings of the 4th International Symposium on Algorithms and Computation*, number 762 in Lecture Notes in Computer Science, pages 240-249, Hong Kong, December 1993. Springer-Verlag. [dvi ] [gzipped Postscript ] **NR95a**-
R. Niedermeier and P. Rossmanith.

On optimal OROW-PRAM algorithms for computing recursively defined functions.*Parallel Processing Letters*, 5(2):299-309, June 1995. [compressed Postscript ] **NR95b**-
R. Niedermeier and P. Rossmanith.

PRAM's towards realistic parallelism: BRAM's.

In H. Reichel, editor,*Proceedings of the 10th Conference on Foundations of Computation Theory*, number 965 in Lecture Notes in Computer Science, pages 363-373, Dresden, Fed. Rep. of Germany, August 1995. Springer-Verlag. [compressed Postscript ] **NR95c**-
R. Niedermeier and P. Rossmanith.

Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits.*Information and Computation*, 118(2):227-245, May 1995. [compressed Postscript ] **NR98a**-
R. Niedermeier and P. Rossmanith.

New upper bounds for MaxSat.

Technical Report KAM-DIMATIA Series 98-401, Faculty of Mathematics and Physics, Charles University, Prague, July 1998.

Extended abstract to appear at ICALP'99, Prague, July 1999. **NR98**-
R. Niedermeier and P. Rossmanith.

Unambiguous computations and locally definable acceptance types.*Theoretical Computer Science*, (194):137-161, 1998. [compressed Postscript ] **NR98b**-
R. Niedermeier and P. Rossmanith.

Upper bounds for vertex cover further improved.

Technical Report KAM-DIMATIA Series 98-411, Faculty of Mathematics and Physics, Charles University, Prague, November 1998. [gzipped Postscript ] **NR99d**-
R. Niedermeier and P. Rossmanith.

An efficient fixed parameter algorithm for 3-hitting set.

Technical Report WSI-99-18, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, October 1999. [gzipped Postscript ] **NR99b**-
R. Niedermeier and P. Rossmanith.

A general method to speed up fixed-parameter-tractable algorithms.

Technical Report TUM-I9913, Institut für Informatik, Technische Universität München, June 1999. [gzipped Postscript ] [Abstract] **NR99c**-
R. Niedermeier and P. Rossmanith.

New upper bounds for MaxSAT.

In J. Wiedermann, P. van Emde Boas, and M. Nielsen, editors,*Proceedings of the 26th International Conference on Automata, Languages, and Programming*, number 1644 in Lecture Notes in Computer Science, pages 575-584. Springer-Verlag, July 1999. **NR99a**-
R. Niedermeier and P. Rossmanith.

Upper bounds for Vertex Cover further improved.

In C. Meinel and S. Tison, editors,*Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science*, number 1563 in Lecture Notes in Computer Science, pages 561-570. Springer-Verlag, 1999. [gzipped Postscript ] **NR00b**-
R. Niedermeier and P. Rossmanith.

A general method to speed up fixed-parameter-tractable algorithms.*Information Processing Letters*, 73(3-4):125-129, 2000. [gzipped Postscript ] [Abstract] **NR00c**-
R. Niedermeier and P. Rossmanith.

New upper bounds for maximum satisfiability.*Journal of Algorithms*, 36:63-88, 2000. [gzipped Postscript ] [Abstract] **NR00a**-
R. Niedermeier and P. Rossmanith.

On efficient fixed parameter algorithms for Weighted Vertex Cover.

In*Proceedings of the 11th International Symposium on Algorithms and Computation*, number 1969 in Lecture Notes in Computer Science, pages 180-191, Taipei, Taiwan, 2000. Springer-Verlag. [gzipped Postscript ] **NR01d**-
R. Niedermeier and P. Rossmanith.

An efficient fixed parameter algorithm for 3-hitting set.*Journal of Discrete Algorithms*, 2001.

To appear. **NR90a**-
I. Niepel and P. Rossmanith.

Uniform circuits and exclusive read PRAMs.

SFB-Bericht 342/31/90A, I9055, Institut für Informatik, Technische Universität München, December 1990. [dvi ] [gzipped Postscript ] [Abstract] **NR91**-
I. Niepel and P. Rossmanith.

Uniform circuits and exclusive read PRAMs.

In S. Biswas and K. V. Nori, editors,*Proceedings of the 11th Conference on Foundations of Software Technology and Theoretical Computer Science*, number 560 in Lecture Notes in Computer Science, pages 307-318, New Delhi, India, December 1991. Springer-Verlag. [dvi ] [gzipped Postscript ] [Abstract] **Ros90b**-
P. Rossmanith.

The owner concept for PRAMs.

SFB-Bericht 342/15/90A, I9028, Institut für Informatik, Technische Universität München, August 1990. [compressed Postscript ] [Abstract] **Ros90a**-
P. Rossmanith.
*Simulation von Parallelen Algorithmen mit exklusivem Speicherzugriff durch Schaltnetze*.

Diplomarbeit, Technische Universität München, 1990. **Ros91**-
P. Rossmanith.

The owner concept for PRAMs.

In C. Choffrut and M. Jantzen, editors,*Proceedings of the 8th Symposium on Theoretical Aspects of Computer Science*, number 480 in Lecture Notes in Computer Science, pages 172-183, Hamburg, Fed. Rep. of Germany, February 1991. Springer-Verlag. [compressed Postscript ] [Abstract] **Ros94b**-
P. Rossmanith.
*Characterizations of Memory Access for PRAM's and Bounds on the Time Complexity of Boolean Functions*.

PhD thesis, Technische Universität München, September 1994. [compressed Postscript ] **Ros95**-
P. Rossmanith.

Separating the unambiguous polynomial time hierarchy by oracles.

Manuscript, November 1995. **Ros99**-
P. Rossmanith.

Learning from random text.

In O. Watanabe and T. Yokomori, editors,*Proceedings of the 10th International Workshop on Algorithmic Learning Theory*, number 1720 in Lecture Notes in Computer Science, pages 132-144. Springer-Verlag, December 1999. [gzipped Postscript ] **RR92**-
P. Rossmanith and W. Rytter.

Observations on log*n*time parallel recognition of unambiguous context-free languages.*Information Processing Letters*, 44:267-272, 1992. [compressed Postscript ] [Abstract] **RZ98b**-
P. Rossmanith and T. Zeugmann.

Learning k-variable pattern languages efficiently stochastic finite on average from positive data.

DOI Technical Report DOI-TR-145, Department of Informatics, Kyushu University, January 1998. [gzipped Postscript ] **RZ98**-
P. Rossmanith and T. Zeugmann.

Learning $k$-variable pattern languages efficiently stochastically finite on average from positive data.

In V. Honavar and G. Slutzki, editors,*Proceedings of the 4th International Colloquium on Grammatical Inference*, number 1433 in Lecture Notes in Artificial Intelligence, pages 13-24. Springer-Verlag, July 1998. [gzipped Postscript ] **RZ01**-
P. Rossmanith and T. Zeugmann.

Stochastic finite learning of the pattern languages.*Machine Learning*, 44(1/2):67-91, 2001. [gzipped Postscript ] [Abstract]