Curriculum Vitae

Dr. Klaus Reinhardt
Date of Birth June 16, 1964 in Stuttgart, Germany
Citizenship: German
Address: Weissdornweg 14/151, 72076 Tübingen, Germany
Office address: Wilhelm-Schickhard Institut für Informatik, Eberhard-Karls-Universität Tübingen, Sand 13, 72076 Tübingen , Germany Tel. +49 7071 29 77566
Email: reinhard@informatik.uni-tuebingen.de
WWW: http://www-fs.informatik.uni-tuebingen.de/~reinhard/

AREAS OF INTEREST

Cryptology (interactive Script), [BR06c]
Secure online-banking [BR07b],[BR07c]
Algorithms and Complexity
Algebraic Methods for Formal Languages
Decidability and complexity questions for formal languages and logic [Rei04b] [LR96] [Rei05] [BR06]
Parameterized Complexity [FHNRR03] [BR04]
Picture Languages
Computational Geometry[AR04] [Rei04c]

EDUCATION

February 2005, Habilitation in Computer Science, University of Tübingen
Thesis: Counting as Method, Model and Task in Theoretical Computer Science [Rei05]
Habilitation-colloquium: February 16, 2005
July 1994, PhD in Computer Science (Dr.rer.nat), University of Stuttgart
Thesis: Priority-multicounter-automata and the synchronization of semitrace-languages [Rei94b]
Date of defence: July 7, 1994
Promoter: Prof. Dr. V. Diekert
September 1989, Diploma (MSc) in Computer Science, University of Stuttgart
Thesis: Hierarchies with alternating pushdown-automata, alternating grammars and finite transducers''
October 1984 - September 1989, Studied computer science, University of Stuttgart with Linguistics and Mathematics as subsidiary subjects
October 1986, Vordiplom (B.S. degree) in Computer Science
,June 1983, Abitur (university-entrance diploma)
September 1974 - June 1983, Highschool: Wilhelmsgymnasium in Stuttgart
Prizes:National Mathematics Competition, Germany (Bundeswettbewerb Mathematik), 1982:
- First price in the first round,
- Third price in the second round.

EMPLOYMENT

since February 2005, Researcher and private lecturer, "Theoretical Computer Science" with Prof. Dr. K.-J. Lange, University of Tübingen
Responsibilities: Teaching, research and examinations
March 1998 - February 2005, Researcher (Wissenschaftlicher Assistent, C1), "Theoretical Computer Science" with Prof. Dr. K.-J. Lange, University of Tübingen
Responsibilities: Teaching and research
October 1994 - February 1998, Researcher, "Theoretical Computer Science" with Prof. Dr. K.-J. Lange, University of Tübingen
worked on the DFG-project "Komet" (Complexity theoretic Methods for the adequate modeling of parallel computations)
October 1989 - September 1994, Research associate (Wissenschaftlicher Mitarbeiter), University of Stuttgart with Prof. Dr. V. Diekert
Responsibilities: Teaching and research
August 1986 - April 1989, Student research assistant Institute for Natural Language Processing of the University of Stuttgart
April 1988 - August 1989, Student teaching assistant (Tutor), Institut for Computer science, University of Stuttgart.

SHORT TERM VISITS

April 2007 - July 2007, Interim professor, University of Trier
March 2000 - June 2000 and September 2002 - August 2003, Visiting researcher, McGill University, Montreal, Canada
worked with Prof. P. McKenzie and Prof. D. Therien
September 1997, visited DIMACS, worked with Prof. E. Allender.
April 1990 - June 1990, Research assistant, Technical University of Munich

TEACHING EXPERIENCE

In Tübingen, I gave lectures in:
- Algorithms (in summer 08),
- Cryptology and Complexity (in summer 95, summer 97, summer 01, winter 03/04, winter 03/04, winter 05/06 and winter 07/08),
- Complexity theory I and II (in winter 95/96 and summer 96),
- Petri Nets (in winter 96/97, winter 99/00, summer 02, summer 04, summer 06 and summer 08),
- Computational Geometry (in winter 97/98, winter 00/01, winter 04/05 and winter 06/07),
- Communication complexity (in summer 89) and
- Datacompression (in summer 05).
I supervised and coordinated the exercices for Informatik III / Theoretical Computer science (in winter 01/02) and seminars in:
- DNA Computing (in winter 98/99),
- Petri Nets (in winter 98/99),
- Cryptology (in summer 04),
- Regular languages (in summer 05) and
- Formal methods in network security (in winter 05/06, summer 06 and winter 06/07).
I initiated and supervised the creation of the Interactive Cryptology Script available under http://www-fs.informatik.uni-tuebingen.de/~reinhard/krypto which enables a user to learn the techniques interactively by self chosen examples.
At the University of Trier, I taught Cryptology and Petri-nets in summer 07.
At McGill University in Montreal, I taught Introduction to Computing 1 using JAVA (in winter, 2003).
As a teaching assistant in Stuttgart 1984-89, I gave lectures in: Automata theory and formal languages, Parallel complexity theory, Recursion theory, Design and analysis of algorithms and data structures and Decidability results for Petri nets. Furthermore I organized exercises and examinations including creating the assignments. In 1988 and 1989 I had already been leading exercise groups as tutor.

RESEARCH ACTIVITIES

During my studies, I did research on semantic interpretation and deduction on discourse representation structures in computer-linguistics from 1986-89 at the Institute for Natural Language Processing of the University of Stuttgart. In my diploma-thesis, I worked on automata and formal languages where close connections to complexity theory were examined [Rei89] [Rei90].

After my studies, I continued the research on automata theory, formal languages [Rei92a], and complexity theory [LR94] [RA97] in Stuttgart. Additionally, I started to work on the theory of traces (which belongs to the field for concurrency and description of distributed systems) [DMR95]. I worked especially on semi-traces and the complexity of problems related to semi-traces [DOR94] [Rei95a]. This also motivated me to prove the decidability of the reachability problem in Petri Nets [Rei04b].

In Stuttgart, I also started to do research on sequential and parallel sorting algorithms, and other algorithms [Rei92b] [KNR99] [NRS97].

During my first years in Tübingen, I was mainly working on parallel complexity theory, which was the main topic of a research project by the DFG from 1990 to 1994 in Munich, where I had already participated. This project was continued since 1995 in Tübingen. The goal of this project was to apply methods of the complexity theory for the modeling and analysis of parallel Algorithms. I found systematic characterizations and appropriate reduction methods for more specific parallel complexity classes [Rei97], [FLR96] and connections of parallelizability and formal languages [Rei99].

Later in Tübingen, I worked on counting problems in complexity theory, showing that NL/poly = UL/poly [RA00], [ARZ99], and picture languages [Rei98], [Rei00].

In Montreal, I started working on Algebraic Methods for Complexity Theory and Formal Languages, Multiparty communication-complexity [PRTT01], injective automata, Church Rosser Congruential Languages [RT03] and binary decision trees.

Later I worked on Computational Geometry [AR04],[Rei04c] and Parametrized Complexity [FHNRR03],[BR06].

Recently I started to work on ideas to enable a secure access to online accounts, for example online banking, in an insecure environment (assuming the adversary to have control over the computer). This resulted so far in 2 patent-applications [BR07b],[BR07c] and ongoing projects with students.

FURTHER PROFESSIONAL ACTIVITIES

I was referee for various conferences and journals like CCC, EUROPAR, FSTTCS, ICALP, LATA, LATIN, DLT, MFCS, STACS, TAPSOFT, Algorithmica, DMTCS, IPL, I\&C, JALC, RAIRO and TCS and I was in the program commitee of the SOFSEM 06.
I organized the 45-th "TheorieTag" of the German GI-group for Complexity in 2002 [Rei02a].
On invitation by Prof. Dr. W. Thomas, I wrote a chapter in the overview book ``Automata Logics and Infinite Games'' [Rei02b].

Membership: EATCS

Hobbies: Archery (AAE), Fencing (FIE), Kendo, Canoe Polo, Kayaking, Snowboarding, Cycling, Hiking, Diving, Teaching Karate 1998-2000

References

AR04: O. Aichholzer. and K. Reinhardt. A quadratic distance bound on sliding between crossing-free spanning trees. In Proc. European Workshop on Computational Geometry EWCG '04, Sevilla, Spain, 2004. [ps, Slides]
AR07: O. Aichholzer. and K. Reinhardt. A quadratic distance bound on sliding between crossing-free spanning trees. Computational Geometry: Theory and Applications, 37(3):155-161, 2007. [ps, Slides]
AR98: E. Allender. and K. Reinhardt. Isolation, Matching, and Counting. In 13 th IEEE Conference on Computational Complexity, pages 92-100, 1998. 1998.
ARZ99: E. Allender, K. Reinhardt, and S. Zhou. Isolation matching and counting uniform amd nonuniform upper bounds. Journal of Computer and System Sciences, 59:164-181, 1999. [pdf]
BR06: Bernd Borchert and K. Reinhardt. Searching paths of constant bandwidth. In Stuller, Wiedermann, editor, Proceedings of the 32nd SOFSEM, number 3831 in LNCS, pages 187-196, 2006. [pdf] A preliminary version appeared as Technical Report WSI-2004-10 Tübingen (Germany), Wilhelm-Schickard-Institut für Informatik, November 2004. [pdf, Slides]
BR06c: Bernd Borchert and K. Reinhardt. Exponential Multiplication Schemes. Technical Report WSI-2006-10 Tübingen (Germany), Wilhelm-Schickard-Institut für Informatik, November 2006. [pdf]
BR07: Bernd Borchert and K. Reinhardt. Deterministically and Sudoku-deterministically recognizable picture languages. in preproceedings of LATA 07. Also appeared as Technical Report WSI-2006-09 Tübingen (Germany), Wilhelm-Schickard-Institut für Informatik, October 2006. [pdf, Slides]
BR07b: Bernd Borchert and K. Reinhardt. Abhör- und manipulationssichere Verschlüsselung für Online Accounts mittels Visueller Krytographie an der Bildschirmoberfläche. Patent application DE-10-2007-018802.3, 2007.
BR07c: Bernd Borchert and K. Reinhardt. Vorrichtung und Verfahren zur abhör- und manipulationssicheren Verschlüsselung von Online Accounts. Patent application DE-10-2007-029759.0, 2007.
BR95: M. Bertol and K. Reinhardt. The tautologies over a finite set are context-free. EATCS Bulletin, 57:196-197, October 1995.
DMR95: Volker Diekert, Anca Muscholl, and Klaus Reinhardt. On codings of traces. In E. W. Mayr, editor, Proceedings of the 12th STACS, number 900 in LNCS, pages 185-196, 1995.[dvi pdf]
DOR94: V. Diekert, E. Ochmanski, and K. Reinhardt. On confluent semi-commutation systems - decidability and complexity results. Information and Computation, 110:164-182, 1994. A preliminary version was presented at ICALP'91, Lecture Notes in Computer Science 510 (1991).
FFOR05: H. Fernau, Rudolf Freund Marion Oswald and K. Reinhardt. Refining the Nonterminal Complexity of Graph-controlled Grammars. Proceedings of the DCFS, pages 110-121. 2005.[pdf.ps]
FHNRR03: H. Fernau, T. Hagerup N. Nishimura P. Ragde and K. Reinhardt. On the parameterized complexity of a generalized Rush Hour puzzle. Proceedings of the 15th Canadian Conference on Computational Geometry, pages 6-9. 2003.[pdf.dvi] [Java]
FLR96a: H. Fernau, K.-J. Lange and K. Reinhardt. Advocating ownership. In V. Chandru, editor, Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science, volume 1180 of LNCS, pages 286-297. Springer, December 1996.
FLR96b: H. Fernau, K.-J. Lange and K. Reinhardt. Advocating ownership. Technical Report WSI-96-32, Universität Tübingen (Germany), Wilhelm-Schickard-Institut für Informatik, October 1996.
FRS99: H. Fernau, K. Reinhardt and L. Staiger. Decidability of Code Properties In W. Thomas, editor, Preproceedings DLT'99, Aachener Informatik-Berichte 99-5, RWTH Aachen, 1999.
FRS00: H. Fernau, K. Reinhardt and L. Staiger. Decidability of Code Properties Martin-Luther-Universit\"at Halle-Wittenberg, Fachbereich Mathematik und Informatik nr .11}, To appear in RAIRO, 2000.
KNRR95: M. Kunde, R. Niedermeier, K. Reinhardt, and P. Rossmanith. Optimal average case sorting on arrays. In E. W. Mayr, editor, Proceedings of the 12th STACS, number 900 in LNCS, pages 503-514, 1995. [pdf]
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 Info rmatik, July 1996. [pdf]
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. [Java] [pdf]
LR94: K.-J. Lange and K. Reinhardt. Empty alternation. In B. Rovan, editor, Proceedings of the 19th Conference on Mathematical Foundations of Computer Science, number 841 in LNCS, pages 494-503, Kosice, Slovakia, August 1994. Springer-Verlag. [dvi pdf]
LR95: K.-J. Lange and K. Reinhardt. Automaten mit der Datenstruktur Menge. In 5. GI Theorietag ``Automaten und Formale Sprachen'', Technical Report 9503, Universität Gießen, Arbeitsgruppe Informatik, pages 159-167, 1995.
LR96: K.-J. Lange and K. Reinhardt. Set automata. In D. S. Bridges, editor, Combinatorics, Complexity and Logic; Proceedings of the DMTCS'96, ISBN 981308314, pages 321-329. Springer, dec 1996.
MRV99: P. McKenzie, K. Reinhardt, and V. Vinai. Circuits and contextfree langauges. Computing and Combinatorics, 5th Annual Internat. Conf. Tokyo, Japan, LNCS 1627, pages 194--203, 1999.
NRS97: R. Niedermeier , K. Reinhardt and P. Sanders . Towards optimal locality in mesh-indexings. Proceedings of the 11th International Symposium on Fundamentals of Computation Theory, number 1279 in LNCS, pages 364--375, Krakow, Poland, September 1997. Springer .[Java] [pdf]
NRS97a: R. Niedermeier , K. Reinhardt and P. Sanders . Towards optimal locality in mesh-indexings. Technical Report Universität Karlsruhe, Fakultät für Informatik, IB 12/97, September 1997. Revised and expanded version of the FCT'97 paper. [dvi pdf]
NRS02: R. Niedermeier , K. Reinhardt and P. Sanders . Towards optimal locality in mesh-indexings. Discrete Applied Mathematics, 117(1--3): 211--237, March 2002. [pdf]
PRTT01: Pavel Pudlak K. Reinhardt and Pascal Tesson Denis Therien Über die Multiparty-Kommunikationskomlexitäat regulärer Sprachen. 11. Theorietag, Automaten und Formale Sprachen, Wendgräben bei Magdeburg, 2001, 93--95. [ps]
RA97: K. Reinhardt and E. Allender. Making Nondeterminism Unambiguous. 38 th IEEE Symposium on Foundations of Computer Science (FOCS), pages 244--253, 1997. [dvi] [ps]
RA00: K. Reinhardt and E. Allender. Making Nondeterminism Unambiguous. SIAM J. Comp. Vol. 29, 2000, 1118--1131. [pdf]
RT03: K. Reinhardt and Denis Therien Some more regular languages that are Church Rosser congruential. 13. Theorietag, Automaten und Formale Sprachen, Herrsching, 200, 97--103. [pdf ps]
Rei89: K. Reinhardt. Hierarchien mit alternierenden Kellerautomaten, alternierenden Grammatiken und finiten Transducern. Diplomarbeit, Universität Stuttgart, Breitwiesenstr. 22, D-70565 Stuttgart, September 1989.
Rei90: K. Reinhardt. Hierarchies over the context-free languages. In J. Dassow and J. Kelemen, editors, 6th IMYSC, number 464 in LNCS, pages 214-224. , 1990. [dvi]
Rei92a: K. Reinhardt. Counting and empty alternating pushdown automata. In J. Dassow, editor, Developments in Theoretical Computer Science: 7th IMYSC, number 6 in Topics in Computer Mathematics, pages 123-132. Gordon and Breach Science Publishes S.A., 1992. [dvi pdf]
Rei92b: K. Reinhardt. Sorting in-place with a worst case complexity of n log n - 1.3 + o(log(n)) comparisons and n log n + o(1) transports. In Ibaraki et al., editor, Proceedings of the 3rd International Symposium on Algorithms and Computation, number 650 in LNCS, pages 489-498. , 1992. [dvi pdf]
Rei94a: K. Reinhardt. Das Erreichbarkeitsproblem bei Petrinetzen mit inhibitorischen Kanten. Manuscript, 1994.
Rei94b: K. Reinhardt. Prioritätszählerautomaten und die Synchronisation von Halbspursprachen. Dissertation, Institut für Informatik, Universität Stuttgart, 1994. [dvi pdf]
Rei95a: K. Reinhardt. On the synchronization of semi-traces. In H. Reichel, editor, 10th FCT, number 965 in LNCS, pages 393-403, Dresden, August 1995. [dvi pdf]
Rei95b: K. Reinhardt. Reachability in Petri Nets with Inhibitor arcs. Manuscript, 1995. [dvi]
Rei96: K. Reinhardt. Reachability in Petri nets with inhibitor arcs. Technical Report WSI-96-30, Universität Tübingen (Germany), Wilhelm-Schickard-Institut für Informatik, 1996.
Rei97: K. Reinhardt. Strict sequential P-completeness. In R. Reischuk, editor, Proceedings of the 14th STACS, number 1200 in LNCS, pages 329-338, Lübeck, February 1997. [dvi pdf]
Rei98: K. Reinhardt. On some recognizable picture-languages. In L. Brim, editor, Proceedings of the 23th MFCS, number 1450 in LNCS, pages 760-770. Springer-Verlag, August 1998. [dvi ps]
Rei99: K. Reinhardt. A parallel contextfree derivation hierarchy. Proceedings of the 12th International Symposium on Fundamentals of Computation Theory, LNCS 1684, pages 441--450, 1999. [dvi ps]
Rei00: K. Reinhardt. The $\#a=\#b$ Pictures are Recognizable. In Proceedings of the 18th STACS, number 2010 in LNCS 2010, pages 527--538, Springer-Verlag, Dresden, 2001. [dvi ps] [Java]
Rei02a: K. Reinhardt. 45. Workshop für Komplexitätstheorie, Datenstrukturen und effiziente Algorithmen (Theorietag). Technical Report WSI-2002-1, Universität Tübingen (Germany), Wilhelm-Schickard-Institut für Informatik, Februar 2002. [ps]
Rei02b: K. Reinhardt. The Complexity of Translating Logic to Finite Automata Grädel, Erich and Thomas, Wolfgang and Wilke, Thomas: Automata, Languages, and Infinite Games, LNCS 2500, pages 231--238, Springer-Verlag, 2002.
Rei04c: K. Reinhardt. Finding the shore of a lake. 2004. [dvi pdf] [Java]
Rei05: K. Reinhardt. Counting as Method, Model and Task in Theoretical Computer Science. Habilitation-thesis, 2005. [pdf]
Rei06: K. Reinhardt. The complexity of the bigamist matching problem. Manuscript, 2006. [pdf]
Rei06b: K. Reinhardt. Reachability in Petri Nets with Inhibitor arcs. revised Manuscript, 2006. [pdf]
Rei07: K. Reinhardt. A tree-height hierarchy of contextfree languages. International Journal of Foundations of Computer Science, 18(6):1383-1394, Dec. 2007.

Given Talks

I gave the talks for the following conference publications: [Rei90], [DOR94], [Rei92a], [Rei92b], [LR94], [DMR95], [Rei95a], [LR96], [Rei97], [RA97], [Rei98], [FRS99], [Rei99], [MRV99], [Rei00], [PRTT01], [Rei02b], [FHNRR03], [RT03], [FFOR05], [BR06] [BR07] and many other talks in seminars and workshops. Further recent talks are the following:

Formale Verifikation von Diffie-Hellman-artigen kryptographischen Protokollen Habilitation colloquium at University of Tuebingen, 15.02.2005
Reachability in Petri Nets with Inhibitor Arcs Seminar talk at McGill University, Montreal, 2.03.2005
Reachability in Petri nets with inhibitor arcs, priority multicounter automata and first order logic with monotone transitive closure Workshop talk at 15. Theorietag: Automaten und Formale Sprachen, Lauterbad, 28.09.2005
The Complexity of the Bigamist Matching Problem Seminar talk at McGill University, Montreal, 13.03.2006
Counting and connectivity in pictures Workshop talk at Advances on Two-dimensional Language Theory, Salerno, 03.05.2006
Logic aspects in Pictures and Petri Nets Invited talk at University of Cottbus, 13.06.2006
Das Rush Hour Puzzle Inaugural lecture at University of Tuebingen, 15.07.2006
Kernals: Annotated, Proper and Induced Conference talk at IWPEC, Zuerich, 15.07.2006
Deterministically and Sudoku-deterministically recognizable picture languages Workshop talk at 16. Theorietag: Automaten und Formale Sprachen, Wien, 28.09.2006
Deterministically and Sudoku-deterministically recognizable picture languages Seminar talk at McGill University, Montreal, 08.01.2007
Logikaspekte in Bildern und Petrinetzen Invited talk at University of Trier, 20.02.2007 []
Logic aspects in Pictures and Petri Nets Invited talk at University of Lulea, 17.07.2007
Reachability in Petri Nets with Inhibitor Arcs Invited talk at University of Quebec, Montreal, 28.09.2007
Ul/poly = NL/poly Lecture at University of Montreal, 2.10.2007
Logikaspekte in Petrinetzen mit Inhibitorkanten Invited talk at University of Aachen, 24.10.2007