Bild mit Unilogo
homeicon uni sucheicon suche kontakticon kontakt impressicon impressum
unilogo Universität Stuttgart 
Institut für Formale Methoden der Informatik

Abteilung Theoretische Informatik


Veröffentlichungen / Publications


From local to global temporal logics over Mazurkiewicz traces

Volker Diekert, Paul Gastin

Theoretical Computer Science 356, 125-135 (2006) pdf File (© Elsevier).

Pure Future Local Temporal Logics are Expressively Complete for Mazurkiewicz Traces

Volker Diekert, Paul Gastin

Information and Computation 204, 1597-1619 (2006) pdf File (© Elsevier).
Conference version, 10 pages: LATIN 2004, LNCS 2976, 170-182 (2004) pdf File (© Springer-Verlag).

Theory of Computing Systems: Special Issue of the 21st International Symposium on Theoretical Aspects of Computer Science

Volker Diekert, Michel Habib (editors)

Theory of Computing Systems, Vol. 39, Springer-Verlag (2006) Springer-Verlag

Partially commutative inverse monoids

Volker Diekert, Markus Lohrey, Alexander Miller

MFCS 2006, LNCS 4162, 292-304, 2006 pdf. File (© Springer-Verlag).

Solvability of Equations in Free Partially Commutative Groups is Decidable

Volker Diekert, Anca Muscholl

International Journal of Algebra and Computation 16 (2006) 1047--1070 pdf File (© World Scientific).
Extended abstract in ICALP 2001, 543--554, LNCS 2076. ps File (© Springer-Verlag).

On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs

Javier Esparza, Petr Jančar, Alexander Miller

Proc. ACSD 2006, 47-56, 2006. pdf file (© IEEE Computer Society).
Tech. report: pdf file.

Infinite-state model-checking of Propositional Dynamic Logics

Stefan Göller, Markus Lohrey

Computer Science LOgic 2006, LNCS 4207, pp.349-364, 2006. ps File pdf File technical report (© Springer-Verlag).

Polynomials, fragments of temporal logic and the variety DA over traces

Manfred Kufleitner

In Oscar H. Ibarra and Zhe Dang, editors, Developments in Language Theory, 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26-29, 2006, Proceedings, volume 4036 of Lecture Notes in Computer Science, pages 37-48. Springer-Verlag, 2006.

Word problems and membership problems on compressed words

Markus Lohrey

SIAM J. Comput., Volume 35, 1210-1240, 2006. pdf File (© SIAM).

First-order and counting theories of omega-automatic structures

Dietrich Kuske, Markus Lohrey

FOSSACS 2006, LNCS 3921, 322-336, 2006 pdf. File (© Springer-Verlag).

Monadic chain logic over iterations and applications to pushdown systems

Dietrich Kuske, Markus Lohrey

LICS 2006, 91--100, 2006 pdf. File (© IEEE Computer Society Press).

Logical Aspects of Cayley-Graphs: The Monoid Case

Dietrich Kuske, Markus Lohrey

International Journal of Algebra and Computation 16, 307-340, 2006. pdf File (© World Scientific).

Querying and Embedding Compressed Texts

Yury Lifshits, Markus Lohrey

MFCS 2006, LNCS 4162, 681-692, 2006 pdf. File (© Springer-Verlag).

The complexity of tree automata and XPath on grammar-compressed trees

Markus Lohrey, Sebastian Maneth

Theoretical Computer Science 363, 196-210, 2006. pdf File (© Elsevier).

Theories of HNN-extensions and amalgamated products

Géraud Sénizergues, Markus Lohrey

ICALP 2006, LNCS 4052, 504-515, 2006 pdf. File (© Springer-Verlag).

Computable Lower Bounds for Busy Beaver Turing Machines

Holger Petersen

In Zoltan Esik, Carlos Martin-Vide und Victor Mitrana (Hrsg.): Recent Advances in Formal Languages and Applications, Springer, 305--319, 2006.

Backing Up in Singly Linked Lists

Amir M. Ben-Amram, Holger Petersen

JACM, Volume 53, 681--705, 2006.

Efficient Simulations by Queue Machines

Holger Petersen, J. M. Robson

SIAM J. Comput., Volume 35, 1059 -- 1069, 2006.