Bild mit Unilogo
homeicon uni sucheicon suche kontakticon kontakt impressicon impressum
unilogo Universität Stuttgart 
Home | Mitarbeiter | Lehre | Forschung | Publikationen | Aktuelles | Institut | Informatik | Fakultät
Institut für Formale Methoden der Informatik

Abteilung Theoretische Informatik
 

Diekert

2013:

Diskrete algebraische Methoden

Volker Diekert, Manfred Kufleitner

Lehrbuch, Walter de Gruyter, 2013.
[Webseite]

Elemente der Diskreten Mathematik

Volker Diekert, Manfred Kufleitner

Lehrbuch, Walter de Gruyter, 2013.
[Webseite]

Efficient algorithms for highly compressed data: The word problem in Higman's group is in P

Volker Diekert, Jürn Laun, Alexander Ushakov

International Journal of Algebra and Computation, Volume 22, Number 8, World Scientific, 2013.
[© World Scientific] [arxiv:1103.1232v1]

2012:

Cyclic rewriting and conjugacy problems

Volker Diekert, Andrew Duncan, Alexei G. Myasnikov

Groups Complexity Cryptology. 4(2) 2012.
[arXiv:1206.4431]

Logspace computations in graph groups and Coxeter groups

Volker Diekert, Jonathan Kausch, Markus Lohrey

Proceedings of LATIN 2012 in Lecture Notes in Computer Science, Volume 7256, Pages 243-254, Springer-Verlag, 2012.
[arXiv:1201.3174v1] [© Springer-Verlag]

Logspace computations in Coxeter groups and graph groups

Volker Diekert, Jonathan Kausch, Markus Lohrey

Computational and Combinatorial Group Theory and Cryptography, volume 582 of Contemporary Mathematics, pages 77-94. Amer. Math. Soc., 2012.
[arXiv:1201.3174v1]

Language theoretical properties of hairpin formations

Volker Diekert, Steffen Kopecki

Theoretical Computer Science, Volume 429, Pages 65-73, Elsevier, 2012.
[© Elsevier]

Deciding regularity of hairpin completions of regular languages in polynomial time

Volker Diekert, Steffen Kopecki, Victor Mitrana

Information and Computation, Volume 217, Pages 12-30, Elsevier, 2012.
[arXiv:11082427v1] [© ScienceDirect]

Bounded synchronization delay in omega-rational expressions

Volker Diekert, Manfred Kufleitner

Computer Science Symposium in Russia (CSR) 2012, Conference Proceedings, volume 7353 of Lecture Notes in Computer Science, pages 89–98, Springer, 2012.

Regular Languages are Church-Rosser Congruential

Volker Diekert, Manfred Kufleitner, Klaus Reinhardt, Tobias Walter

Automata, Languages, and Programming, Lecture Notes in Computer Science, Volume 7392, Pages 177-188, Springer-Verlag, 2012.
[arXiv:1202.1148v1] [© Springer-Verlag]

This contribution received the best paper award in track B.

The Krohn-Rhodes Theorem and Local Divisors

Volker Diekert, Manfred Kufleitner, Benjamin Steinberg

Fundamenta Informaticae, Volume 116, Pages 65-77, IOS Press, 2012.
[arXiv:1111.1585v1] [© IOS Press]

Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P

Volker Diekert, Jürn Laun, Alexander Ushakov

Proceedings of the Symposium on Theoretical Aspects of Computer Science 2012 (STACS), 2012.
[pdf File on LIPIcs]

Context-Free Groups and Their Structure Trees

Volker Diekert, Armin Weiß

Preprint, 2012.
[arXiv:1202.3276v4]

2011:

Marriage Broker

Volker Claus, Volker Diekert, Holger Petersen

In: Algorithms Unplugged, Chapter 35, Pages 345-355, 2011.
[Springer-Verlag]

It is NL-complete to Decide Whether a Hairpin Completion of Regular Languages Is Regular

Volker Diekert, Steffen Kopecki

International Journal of Foundations of Computer Science (IJFCS), Volume 22, Issue 8, Pages 1813-1828, World Scientific, 2011.
[arXiv:1101.4824v1] [© World Scientific]

Fragments of First-Order Logic over Infinite Words

Volker Diekert, Manfred Kufleitner

Theory of Computing Systems, Vol. 48(3), Springer-Verlag (2011)
[arXiv] [http] [© Springer-Verlag]

Star-Free Languages are Church-Rosser Congruential

Volker Diekert, Manfred Kufleitner, Pascal Weil

Preprint, 2011.
[arXiv:1111.4300v1]

On Computing Geodesics in Baumslag-Solitar Groups

Volker Diekert, Jürn Laun

International Journal of Algebra and Computation, Volume 21, Pages 119-145, Number 1-2, World Scientific, 2011.
[arxiv:0907.5114v2] [© World Scientific]

Trace Theory

Volker Diekert, Anca Muscholl

In: Encyclopedia of Parallel Computing, Part 20, Pages 2071-2079, Springer-Verlag, 2011.
[pdf] [© Springer-Verlag]

Solving Word Problems in Group Extensions over Infinite Words

Volker Diekert, Alexei G. Myasnikov

Developments in Language Theory (DLT) 2011, Conference Proceedings, Volume 6795 of Lecture Notes in Computer Science, Pages 192-203, Springer-Verlag, 2011.
[arXiv:1011.2024v2] [© Springer-Verlag]

2010:

Theory of Computing Systems: Special Issue, 2010.

Sergei Artemov, Volker Diekert, Dima Grigoriev (editors)

Theory of Computing Systems, Vol. 46, Springer-Verlag (2010). Springer-Verlag

Theory of Computing Systems: Special Issue, 2010.

Sergei Artemov, Volker Diekert, Alexander Razborov (editors)

Theory of Computing Systems, Vol. 46, No. 4, Springer-Verlag (2008). Springer-Verlag

Geodesic rewriting systems and pregroups

Volker Diekert, Andrew J. Duncan and Alexei Miasnikov

Combinatorial and Geometric Group Theory (2010). In: Bogopolski, Bumagin, Kharlampovich, Ventura (Eds.): Combinatorial and Geometric Group Theory, Trends in Mathematics, Springer, 55-91, 2010. pdf File (©Springer)

Weinbaum Factorizations of Primitive Words

Volker Diekert, Tero Harju, Dirk Nowotka

russian version: Izvestiya VUZ. Matematika, (1):21-33, 2010. pdf file (© Kasan State University).
english version: Russian Mathematics, 54(1):16-25, 2010. pdf file (© Springer-Verlag),
Conference version: 10 pages: WOWA Workshop St. Petersburg (Russia) 2006
Technical Report: TUCS No 780, September 2006 (Turku Center for Computer Science))

Complexity Results and the Growths of Hairpin Completions of Regular Languages

Volker Diekert, Steffen Kopecki

In M. Domaratzki and K. Salomaa (editors), Implementation and Application of Automata - 15th International Conference, CIAA 2010, volume 6482 of LNCS, pages 105-114. Springer, 2011.
[Technical Report] [Springer]

2009:

Local safety and local liveness for distributed systems

Volker Diekert, Paul Gastin

In Lodaya, Mukund, and Ramanujam, editors, Perspectives in Concurrency Theory, Universities Press, IARCS-Universities, pages 86-106, 2009 pdf File

Komplexität der Geographie

Volker Diekert, Ulrich Hertrampf

In Diekert, Weicker, and Weicker, editors, Informatik als Dialog zwischen Theorie und Anwendung, Vieweg+Teubner, pages 119-132, 2009 pdf File (©Vieweg+Teubner)

On the Hairpin Completion of Regular Languages

Volker Diekert, Steffen Kopecki, Victor Mitrana

In M. Leucker and C. Morgan, editors, ICTAC, volume 5684 of Lecture Notes in Computer Science, pages 170-184. Springer, 2009.
[Springer]

Some remarks about stabilizers

Volker Diekert, Dalia Krieger

Theoretical Computer Science 410, 30-32 (2009) pdf File (© Elsevier).

Fragments of First-Order Logic over Infinite Words (Extended Abstract)

Volker Diekert, Manfred Kufleitner

In Susanne Albers and Jean-Yves Marion, editors, 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, Freiburg, Germany, February 26-28, 2009, Proceedings, pages 325-336. pdf File (full version).

Fragments of First-Order Logic over Infinite Words

Volker Diekert, Manfred Kufleitner

Technical Report No. 2009/04, Computer Science, Universität Stuttgart.
http and arXiv:0906:2995 [cs.FL].

Variationen über Walther von Dyck und Dyck-Sprachen

Volker Diekert, Klaus-Jörn Lange

In Diekert, Weicker, and Weicker, editors, Informatik als Dialog zwischen Theorie und Anwendung, Vieweg+Teubner, pages 147-154, 2009 pdf File (©Vieweg+Teubner)

Developments in Language Theory, 13th International Conference, DLT 2009, Stuttgart, Germany, 2009.

Volker Diekert, Dirk Nowotka (editors)

Lecture Notes in Computer Science, Vol. 5583, Springer-Verlag (2009). Springer-Verlag

Informatik als Dialog zwischen Theorie und Anwendung: Festschrift für Volker Claus zum 65. Geburtstag.

Volker Diekert, Karsten Weicker, Nicole Weicker (editors)

Vieweg+Teubner (2009). Vieweg+Teubner

2008:

Theory of Computing Systems: Special Issue of the 1st International Symposium on Computer Science in Russia, St. Petersburg 2006.

Sergei Artemov, Volker Diekert, Dima Grigoriev (editors)

Theory of Computing Systems, Vol. 43, No. 2, Springer-Verlag (2008). Springer-Verlag

Partnerschaftsvermittlung

Volker Claus, Volker Diekert, Holger Petersen

In: Taschenbuch der Algorithmen, Kapitel 37, 373-384 pdf File (© Springer-Verlag).

First-order definable languages

Volker Diekert, Paul Gastin

In: Logic and Automata: History and Perspective (Eds. J. Flum and E. Grädel and Th. Wilke) Amsterdam University Press, Texts in Logic and Games (2008) 261--306 pdf File

A Survey on Small Fragments of First-Order Logic over Finite Words

Volker Diekert, Paul Gastin, Manfred Kufleitner

International Journal of Foundations of Computer Science, 19(3): 513-548, 2008. pdf File (© World Scientific).

Word equations over graph products

Volker Diekert, Markus Lohrey

International Journal of Algebra and Computation 18 (2008) 493 - 533. pdf File (© World Scientific).
Conference version: FSTTCS 2003, LNCS 2914 (2003) 156-167.

Partially commutative inverse monoids

Volker Diekert, Markus Lohrey, Alexander Miller

Semigroup Forum 77(2), 196-226, 2008. Link (© Springer-Verlag).
Conference version: MFCS 2006, LNCS 4162, 292-304 (2006).

Algorithmic problems on inverse monoids over virtually-free groups

Volker Diekert, Markus Lohrey, Nicole Ondrusch

International Journal of Algebra and Computation 18 (2008) 181-208 pdf File (© World Scientific).

2007:

On first-order fragments for Mazurkiewicz traces

Volker Diekert, Martin Horsch, Manfred Kufleitner

Fundamenta Informaticae, 80(1-3):1-29, 2007. pdf File (© IOS Press).

On first-order fragments for words and Mazurkiewicz traces: A survey

Volker Diekert, Manfred Kufleitner

DLT 2007. In Tero Harju, Juhani Karhumäki, and Arto Lepistö, editors, Proceedings Developments in Language Theory, 11th International Conference, DLT 2007, Turku, Finland, July 3-6, 2007, Lecture Notes in Computer Science, Vol 4588 (2007) 1-19. pdf File (© Springer-Verlag).

Computer Science - Theory and Applications. Proceedings

Second International Symposium on Computer Science in Russia, CSR 2007, Ekaterinburg, Russia, September 3-7, 2007.

Volker Diekert, Mikhail V. Volkov, Andrei Voronkov (editors)

Lecture Notes in Computer Science, Vol. 4649, Springer-Verlag (2007) Springer-Verlag

2006:

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).

2005:

Regular Frequency Computations

Holger Austinat, Volker Diekert, Ulrich Hertrampf, Holger Petersen

Theoretical Computer Science, vol. 330, no. 1, pp. 15-21 (2005) pdf File (© Elsevier).

Proceedings of the 22nd International Symposium on Theoretical Aspects of Computer Science

Volker Diekert, Bruno Durand (editors)

Lecture Notes in Computer Science, Vol. 3404, Springer-Verlag (2005) Springer-Verlag

The existential theory of equations with rational constraints in free groups is PSPACE-complete

Volker Diekert, Claudio Gutiérrez, Christian Hagenah

Information and Computation 202: 105-140, 2005 pdf File (© Elsevier).
Extended abstract in STACS 2001, LNCS 2010, 170-182 (2001). ps File (© Springer-Verlag).

2004:

Local Temporal Logic is Expressively Complete for Cograph Dependence Alphabets

Volker Diekert, Paul Gastin

Information and Computation 195, 30-52 (2004) pdf File (© Elsevier).

Pure Future Local Temporal Logics are Expressively Complete for Mazurkiewicz Traces

Volker Diekert, Paul Gastin

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

Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science

Volker Diekert, Michel Habib (editors)

Lecture Notes in Computer Science, Vol. 2996, Springer-Verlag (2004) Springer-Verlag

Existential and Positive Theories of Equations in Graph Products

Volker Diekert, Markus Lohrey

Theory of Computing Systems 37, 133-156, 2004 pdf File (© Springer-Verlag).

2003:

A Remark about Quadratic Trace Equations

Volker Diekert, Manfred Kufleitner

DLT 2002, 59-66, LNCS 2450, 2003. ps File (© Springer-Verlag).

Word equations over graph products

Volker Diekert, Markus Lohrey

FSTTCS 2003, LNCS 2914, 156-167 ps File (© Springer-Verlag).

2002:

A Structural Property of Regular Frequency Computations

Holger Austinat, Volker Diekert, Ulrich Hertrampf

Theoretical Computer Science, vol. 292, no. 1, pp. 33-43 (2003) ps File (© Elsevier).

A Pure Future Local Temporal Logic Beyond Cograph-Monoids

Volker Diekert

Proc. of RIMS Symposium on Algebraic Systems, Formal Languages and Conventional and Unconventional Computation Theory, 2002 ps. File

Makanin's Algorithm

Volker Diekert

In Algebraic Combinatorics on Words, M. Lothaire, chapter 12, Cambridge University Press, 387--442, (2002) ps File

Safety and Liveness Properties for Real Traces and a Direct Translation from LTL to Monoids

Volker Diekert, Paul Gastin

Formal and Natural Computing --- Essays Dedicated to Grzegorz Rozenberg, LNCS 2300, 26-38. ps. File (© Springer-Verlag).

LTL is expressively complete for Mazurkiewicz traces.

Volker Diekert, Paul Gastin

J. Comput. Syst. Sci. 64, 396--418 (2002) pdf File (© Elsevier).

Existential and Positive Theories of Equations in Graph Products

Volker Diekert, Markus Lohrey

STACS 2002, LNCS 2285, 501-512 ps File (© Springer-Verlag).

A note on the existential theory of equations in plain groups

Volker Diekert, Markus Lohrey

International Journal of Algebra and Computation 12, 1-7, 2002. pdf File (© World Scientific).

2001:

The existential theory of equations with rational constraints in free groups is PSPACE-complete

Volker Diekert, Claudio Gutiérrez, Christian Hagenah

STACS 2001, LNCS 2010, 170-182 (2001). ps File (© Springer-Verlag).

Solvability of Equations in Free Partially Commutative Groups is Decidable

Volker Diekert, Anca Muscholl

ICALP 2001, 543--554, LNCS 2076. ps File (© Springer-Verlag).

2000:

LTL Is Expressively Complete for Mazurkiewicz Traces

Volker Diekert, Paul Gastin

ICALP 2000, LNCS 1853, 211-222, 2000. ps File (© Springer-Verlag).

1999:

An expressively complete temporal logic without past tense operators for Mazurkiewicz traces

Volker Diekert, Paul Gastin

CSL' 99, LNCS 1683, 188-203, 1999. ps File (© Springer-Verlag).

Solving word equations modulo partial commutations

Volker Diekert, Yuri Matiyasevich, Anca Muscholl

Theoretical Computer Science 224, 215-235, 1999. ps File (© Elsevier).

Quadratic word equations

Volker Diekert, John Michael Robson

In Jewels are forever - Contributions on Theoretical Computer Science, in Honor of Arto Salomaa, Springer, 314--326, 1999 ps File (© Springer-Verlag).

On quadratic word equations

John Michael Robson, Volker Diekert

STACS' 99, LNCS 1563, 217-226, 1999. ps File (© Springer-Verlag).

1998:

Characterization of the expressive power of silent transitions in timed automata

Beatrice Bérard, Volker Diekert, Paul Gastin, Antoine Petit

Fundamenta Informaticae 36, 145-182, 1998. ps File (© IOS Press).

Approximating traces

Volker Diekert, Paul Gastin

Acta Informatica 35 (1998) 567-593. ps File (© Springer-Verlag).

Some Identies Related to Automata, Determinants, and Möbius Functions

Volker Diekert und Yuji Kobayashi

ps File

1997:

A Remark on Trace Equations

Volker Diekert

Foundations of Computer Science: Potential - Theory - Cognition, LNCS 1337, 251-260, 1997.

Removing $\varepsilon$-Transitions in Timed Automata

Volker Diekert, Paul Gastin, Antoine Petit

STACS'97, LNCS 1200, 583-594, 1997. ps File (© Springer-Verlag).

Solving trace equations using lexicographical normal forms

Volker Diekert, Yuri Matiyasevich, Anca Muscholl

ICALP'97 (Bologna, Italy) Abstract, BibTeX entry, dvi File, ps.Z File (© Springer-Verlag).

Partial Commutation and Traces.

Volker Diekert, Yves Métivier

In G. Rozenberg (Editor), Handbook on Formal Languages, Volume III, 457-534, 1997.

1996:

Trace rewriting: Computing normal forms in time O(n log n)

Michael Bertol, Volker Diekert

Proceedings of the "13th Symposium on Theoretical Aspects of Computer Science (STACS)" LNCS 1046, 269-280, Springer 1996, ps File. ps.gz File (© Springer-Verlag).

A note on Metivier's construction of asynchronous automata for triangulated graphs

Volker Diekert, Anca Muscholl

Fundamenta Informaticae 25 (1996), Special Issue on Formal Languages. Abstract, BibTeX entry, dvi File, ps.Z File (© IOS Press).

Code problems on traces

Volker Diekert, Anca Muscholl

MFCS'96 (Crakow Poland), Invited Lecture Abstract, BibTeX entry, dvi File, ps.Z File (© Springer-Verlag).

1995:

A domain for concurrent termination: A generalization of Mazurkiewicz traces

Volker Diekert, Paul Gastin

ICALP'95, LNCS 944, 15-26. dvi File, ps.Z File (© Springer-Verlag).

Rational and recognizable complex trace languages

Volker Diekert, Paul Gastin, Antoine Petit

Information and Computation 116, 134-153, 1995.

Recent developments in trace theory

Volker Diekert, Paul Gastin, Antoine Petit

Proceedings of the 2nd Conference on Developments in Language Theory (DLT'95), 373-385, 1995.

On Codings of Traces

Volker Diekert, Anca Muscholl, Klaus Reinhardt

STACS'95, LNCS 900, 1995. Abstract, BibTeX entry, dvi File, ps.Z File (© Springer-Verlag).

The Book of Traces

Volker Diekert, Grzegorz Rozenberg (editors)

World Scientific, Singapore, 1995.

Description, BibTeX entry, Table of Contents (dvi file).

On Confluence of One-Rule Trace-Rewriting Systems

Celia Wrathall, Volker Diekert

MST 28, 341-361, 1995.

1994:

On efficient reduction-algorithms for some trace rewriting systems

Michael Bertol, Volker Diekert

Proceedings of "Term Rewriting", LNCS 909, 114-126, Springer 1993 ps File.ps.gz File (© Springer-Verlag).

A partial trace semantics for Petri nets

Volker Diekert

TCS 134, 87-105, 1994.

On confluent semi-commutation systems - decidability and complexity results

Volker Diekert, Edward Ochmanski, Klaus Reinhardt

Information and Computation 110, 164-182, 1994.

1993:

On the concatenation of infinite traces

Volker Diekert

TCS 113, 35-54, 1993.

Möbius functions and confluent semi-commutations

Volker Diekert

TCS 108, 25-43, 1993.

Rewriting, semi-commutations, and Möbius functions

Volker Diekert

FCT'93, LNCS 710, pp. 1-15, 1993. Abstract, BibTeX entry.

Complex and complex-like traces

Volker Diekert

MFCS'93, LNCS 711, pp. 68-82 1993. Abstract, BibTeX entry.

Deterministic asynchronous automata for infinite traces

Volker Diekert, Anca Muscholl

STACS'93, LNCS 665. Extended version in Acta Informatica vol. 31 (1994) Abstract, BibTeX entry, dvi File, ps.Z File.

1991:

On inherently context-sensitive languages - An application of complexity cores

Ronald V. Book, Volker Diekert

Information Processing Letters 40, 21-23, 1991.

Recognizable complex trace languages

Volker Diekert, Paul Gastin, Antoine Petit

MFCS'91, LNCS 520, 131-140, 1991.

1990:

Research topics in the theory of free partially commutative monoids

Volker Diekert

BEATCS 40, 479-491, 1990.

Combinatorics on Traces

Volker Diekert

LNCS 454, 1990.

Combinatorial rewriting on traces

Volker Diekert

STACS'90, LNCS 415, 138-151, 1990.

Word problems over traces which are solvable in linear time

Volker Diekert

TCS 74, 3-18, 1990.
 
Letzte Änderung 16. Apr 14:01 |  © Universität Stuttgart | Impressum