Forschungsbericht

Research focus:

Lehrstuhl für Informatik IV
Institut für Informatik, 97074 Würzburg
Mail: wagner@informatik.uni-wuerzburg.de
Url: http://theoretische.informatik.uni-wuerzburg.de

Scientific members:

Scientific assistants:

Other participating persons and organisations:

Prof. Dr. Pierre McKenzie ,Mail: mckenzie@iro.umontreal.ca
Prof. Dr. Thomas Schwentick ,Tel: 06421 28 21532,Fax: 06421 28 25419,Mail: tick@informatik.uni-marburg.de
Prof. Dr. Denis Therien ,Mail: denis@cs.mcgill.ca
Prof. Dr. Clemens Lautemann ,Tel: 06131 39-3334,Fax: 06131 39-3534,Mail: cl@informatik.uni-mainz.de
Timo Peichl

Research foci (and basic equipment-based research projects):
Model theoretical characterisation of complexity classes

Results:
We refer to the following papers:

M. Galota und H. Vollmer:
"A generalization of the Büchi-Elgot-Trakhtenbrot-Theorem"
In Proceedings 15th Computer Science Logic 2001
Volume 2142 of Lecture Notes in Computer Science
pages 355-368
Springer Verlag, 2001.

P. McKenzie, T. Schwentick, D. Therien, H. Vollmer:
"The many faces of a translation"
Proceedings 27th International Colloquium on Automata
Languages and Programming
Volume 1853 of Lecture Notes in Computer Science
pages 890-901
Springer Verlag, 2000.

T. Peichl, H. Vollmer:
"Finite automata with generalized acceptance criteria"
Discrete Mathematics and Theoretical Computer Science 4
pages 179-92
2001

C. Lautemann, P. McKenzie, T. Schwentick, H. Vollmer:
"The descriptive complexity approach to LOGCFL"
Journal of Computer and System Sciences 62(4)
Seiten 629-652
2001.