suche

kontakt

impressum

Universität Stuttgart

	Institut für Formale Methoden der Informatik
	Abteilung Theoretische Informatik

Veröffentlichungen / Publications

A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time

E. Allender, R. Beigel, U. Hertrampf, S. Homer

7th Symp. on Theoretical Aspects of Computer Science, LNCS 415, 1 - 11, 1990.

Almost-everywhere Complexity Hierarchies for Nondeterministic Time

E. Allender, R. Beigel, U. Hertrampf, S. Homer

Theoretical Computer Science 115(2), 225 - 242, 1993.

On the Power of Uniform Families of Constant Depth Threshold Circuits

E. Allender, U. Hertrampf

15th Symp. on Mathematical Foundations of Computer Science, LNCS 452, 158 - 164, 1990.

Depth Reduction for Circuits of Unbounded Fan-In

E. Allender, U. Hertrampf

Information and Computation 112(2), 217 - 238, 1994.

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

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

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

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

Structure and Importance of Logspace-MOD-Classes

G. Buntrock, C. Damm, U. Hertrampf, C. Meinel

Mathematical Systems Theory 25, 223 - 237, 1992.

Counting Classes: Thresholds, Parity, Mods, and Fewness

R. Beigel, J. Gill, U. Hertrampf

7th Symp. on Theoretical Aspects of Computer Science, LNCS 415, 49 - 57, 1990.

Efficient rewriting in cograph trace monoids

Michael Bertol

Proceedings of the 10th Fundamentals of Computation Theory (FCT '95), Dresden (Germany) 1995 ps File. ps.gz File (© Springer-Verlag).

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

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

Nonfinite Aximatizability of the Equational Theory of Shuffle

Zoltán Ésik, Michael Bertol

Acta Informatica 35(6), 505-539 (1998) ps File. ps.gz File (© Springer-Verlag).

The Tautologies over a finite set are context-free

Michael Bertol, Klaus Reinhardt

Bulletin of the European Association for Theoretical Computer Science Number 57. ps File. ps.gz File.

Classification tree sources

Edgar Binder and Manfred Kufleitner

In IEEE Information Theory Workshop 2009, ITW 2009, Taormina, Sicily, October 11-16, 2009, Proceedings. IEEE, 2009.

Combining models in data compression

Manfred Kufleitner, Edgar Binder, Alexander Fries

In Tjalling Tjalkens and Frans Willems, editors, Proceedings of the 30th Symposium on Information Theory in the Benelux, Eindhoven, The Netherlands, May 28-29, 2009, pages 135-142, 2009.

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

Ronald V. Book, Volker Diekert

Information Processing Letters 40, 21-23, 1991.

The Chain Method to Separate Counting Classes.

K. Cronauer, U. Hertrampf, H. Vollmer, K.W. Wagner

Theory of Computing Systems 31, 93 - 108, 1998.

Partnerschaftsvermittlung

Volker Claus, Volker Diekert, Holger Petersen

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

Marriage Broker

Volker Claus, Volker Diekert, Holger Petersen

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

Rankers over Infinite Words (Extended Abstract)

Luc Dartois, Manfred Kufleitner, Alexander Lauser

Developments in Language Theory (DLT) 2010, Conference Proceedings, volume 6224 of Lecture Notes in Computer Science, pages 148–159. Springer, 2010.
[pdf] [http] [© Springer-Verlag]

Rankers over Infinite Words

Luc Dartois, Manfred Kufleitner, Alexander Lauser

Technical Report No. 2010/01, Computer Science, Universität Stuttgart.
[http] [arXiv]

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.

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.

A partial trace semantics for Petri nets

Volker Diekert

TCS 134, 87-105, 1994.

A Remark on Trace Equations

Volker Diekert

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

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

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

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)

Cyclic rewriting and conjugacy problems

Volker Diekert, Andrew Duncan, Alexei G. Myasnikov

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

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

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

Approximating traces

Volker Diekert, Paul Gastin

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

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

LTL Is Expressively Complete for Mazurkiewicz Traces

Volker Diekert, Paul Gastin

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

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

From local to global temporal logics over Mazurkiewicz traces

Volker Diekert, Paul Gastin

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

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

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

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

LTL is expressively complete for Mazurkiewicz traces.

Volker Diekert, Paul Gastin

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

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

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

Recognizable complex trace languages

Volker Diekert, Paul Gastin, Antoine Petit

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

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.

Removing $\varepsilon$-Transitions in Timed Automata

Volker Diekert, Paul Gastin, Antoine Petit

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

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

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

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

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

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

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

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 first-order fragments for Mazurkiewicz traces

Volker Diekert, Martin Horsch, Manfred Kufleitner

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

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]

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

Volker Diekert und Yuji Kobayashi

ps File

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]

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]

Language theoretical properties of hairpin formations

Volker Diekert, Steffen Kopecki

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

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]

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]

Some remarks about stabilizers

Volker Diekert, Dalia Krieger

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

A Remark about Quadratic Trace Equations

Volker Diekert, Manfred Kufleitner

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

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

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

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]

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.

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]

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]

Star-Free Languages are Church-Rosser Congruential

Volker Diekert, Manfred Kufleitner, Pascal Weil

Preprint, 2011.
[arXiv:1111.4300v1]

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)

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]

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]

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]

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

Word equations over graph products

Volker Diekert, Markus Lohrey

FSTTCS 2003, LNCS 2914, 156-167 ps File (© 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).

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

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

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

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

Solving word equations modulo partial commutations

Volker Diekert, Yuri Matiyasevich, Anca Muscholl

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

Partial Commutation and Traces.

Volker Diekert, Yves Métivier

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

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.

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

Solvability of Equations in Free Partially Commutative Groups is Decidable

Volker Diekert, Anca Muscholl

ICALP 2001, 543--554, LNCS 2076. ps 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).

Trace Theory

Volker Diekert, Anca Muscholl

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

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

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]

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

On confluent semi-commutation systems - decidability and complexity results

Volker Diekert, Edward Ochmanski, Klaus Reinhardt

Information and Computation 110, 164-182, 1994.

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

The Book of Traces

Volker Diekert, Grzegorz Rozenberg (editors)

World Scientific, Singapore, 1995.

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

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

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

Context-Free Groups and Their Structure Trees

Volker Diekert, Armin Weiß

Preprint, 2012.
[arXiv:1202.3276v4]

On Confluence of One-Rule Trace-Rewriting Systems

Celia Wrathall, Volker Diekert

MST 28, 341-361, 1995.

Unbordered Factors and Lyndon Words

Jean-Pierre Duval, Tero Harju, Dirk Nowotka

Discrete Mathematics, 308(11):2261-2264, 2008. pdf File (© Elsevier).

On logical definability of omega-trace languages

Werner Ebinger

Proc. ASMICS Workshop Infinite Traces, Tübingen 1992. Universität Stuttgart, Fakultät Informatik, 1992. Abstract, BibTeX entry, README

Charakterisierung von Sprachklassen unendlicher Spuren durch Logiken

Werner Ebinger

Dissertation, Universität Stuttgart, Fakultät Informatik, 1994.

Logical Definability on Infinite Traces

Werner Ebinger, Anca Muscholl

Theoretical Computer Science 154 (1996) (Preliminary version ICALP '93, LNCS 700, 1993.) Abstract, BibTeX entry, dvi File, ps.Z File.

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.

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

Javier Esparza, Petr Jančar, Alexander Miller

Fundamenta Informaticae 86(3), 227-253, 2008. pdf file, abstract (© IOS Press).
Conference version: Proc. ACSD 2006, 47-56 (2006).

On smoothed analysis of quicksort and Hoare's find

Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi

In Hung Quang Ngo, editor, 15th International Computing and Combinatorics Conference (COCOON 2009), Niagara Falls, New York, U.S.A., July 13-15, 2009, Proceedings, volume 5609 of Lecture Notes in Computer Science, pages 158-167. Springer-Verlag, 2009.

On the Complexity of Reasoning about Dynamic Policies

Stefan Göller

Computer Science Logic 2007, to appear ps File pdf File (© Springer-Verlag).

Fixpoint logics on hierarchical structures

Stefan Göller, Markus Lohrey

FST&TCS 2005, LNCS 3821, pp.483-494, 2005. ps File pdf File technical report (© Springer-Verlag).

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

PDL with Intersection and Converse is 2EXP-complete

Stefan Göller, Markus Lohrey, Carsten Lutz

FoSSaCS, LNCS 4423, pp.198-212, 2007. ps File pdf File (© Springer-Verlag).

A Note on an Extension of PDL

Stefan Göller, Dirk Nowotka

Journal of the Applied Logic, 6(4):606-608, 2008. pdf File (© Elsevier).

Computing $\eps$-Free NFA from Regular Expressions in $O(n \log^2(n))$ Time

Christian Hagenah, Anca Muscholl

MFCS'98, LNCS 1450, pp.277-285 Abstract, BibTeX entry, dvi File, ps.gz File (© Springer-Verlag).

Periodicity and Unbordered Words: A Proof of the Extended Duval Conjecture

Tero Harju, Dirk Nowotka

Journal of the ACM, 54(4):20, 2007. pdf File (© ACM).
Conference version: STACS 2004

Bordered Conjugates of Words over Large Alphabets

Tero Harju, Dirk Nowotka

Electronic Journal of Combinatorics, 15(1):N41, 2008. pdf File

Cyclically Repetition-free Words on Small Alphabets

Tero Harju, Dirk Nowotka

Information Processing Letters, to appear, 2010. pdf File (© Elsevier).

Relations among MOD-Classes

U. Hertrampf

Theoretical Computer Science 74, 325 - 329, 1990.

Locally Definable Acceptance Types - The Three-Valued Case

U. Hertrampf

1st Latin American Symp. on Theoretical Informatics, LNCS 583, 262 - 271, 1992.

Locally Definable Acceptance Types for Polynomial Time Machines

U. Hertrampf

9th Symp. on Theoretical Aspects of Computer Science, LNCS 577, 199 - 207, 1992.

Complexity Classed Defined via k-valued Functions

U. Hertrampf

9th Conference on Structure in Complexity Theory, IEEE Computer Society Press, 224 - 234, 1994.

Complexity Classes with Finite Acceptance Type

U. Hertrampf

11th Symp. on Theoretical Aspects of Computer Science, LNCS 775, 543 - 553, 1994.

Classes of Bounded Counting Type and their Inclusion Relations

U. Hertrampf

12th Symp. on Theoretical Aspects of Computer Science, LNCS 900, 60 - 70, 1995.

Acceptance by Transformation Monoids (with an Application to Local Self Reductions)

U. Hertrampf

12th Conference on Computational Complexity, IEEE Computer Society Press, 213 - 224, 1997.

Polynomial Time Machines Equipped with Word Problems over Algebraic Structures as their Acceptance Criteria

U. Hertrampf

11th International Symposium on Fundamentals of Computation Theory, LNCS 1279, 233 - 244, 1997.

The Shapes of Trees

U. Hertrampf

3rd International Computing and Combinatorics Conference, LNCS 1276, 412 - 421, 1997.

The Inherent Dimension of Bounded Counting Classes

U. Hertrampf

4th International Computing and Combinatorics Conference, LNCS 1449, 157 - 166, 1998.

Generalized Regular Counting Classes

U. Hertrampf

24th Symposium on Mathematical Foundations of Computer Science, MFCS 99, LNCS 1672, 419 - 429, 1999.

On the Power of Polynomial Time Bit-Reductions

U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer, K.W. Wagner

8th Conference on Structure in Complexity Theory, IEEE Computer Society Press, 200 - 207, 1993.

On the Power of Number-theoretic Operations with respect to Counting

U. Hertrampf, H. Vollmer, K.W. Wagner

10th Conference on Structure in Complexity Theory, IEEE Computer Society Press, 299 - 314, 1995.

On Balanced vs. Unbalanced Computation Trees

U. Hertrampf, H. Vollmer, K.W. Wagner

Mathematical Systems Theory 29, 411 - 421, 1996.

Interactive Proof Systems: Provers, Rounds, and Error Bounds

U. Hertrampf, K.W. Wagner

4th Workshop Computer Science Logic, CSL '90, LNCS 533, 261 - 273, 1991.

Maximal Intersection Queries in Randomized Input Models

Benjamin Hoffmann, Mikhail Lifshits, Yury Lifshits, Dirk Nowotka

Theory of Computing Systems, 46(1): 104-119, 2009 pdf File (© Springer-Verlag).
Conference version: CSR 2007

Maximal Intersection Queries in Randomized Graph Models

Benjamin Hoffmann, Yury Lifshits, Dirk Nowotka

2nd International Computer Science Symposium in Russia 2007, LNCS 4649 ps File pdf File (© Springer-Verlag).

On the Relation between Periodicity and Unbordered Factors of Finite Words

Štěpán Holub, Dirk Nowotka

DLT 2008, LNCS 5257, 408-418, 2008. pdf File (© Springer-Verlag).

The Ehrenfeucht Silberger Problem

Štěpán Holub, Dirk Nowotka

ICALP 2009, LNCS 5555, 537-548, 2009. pdf File (© Springer-Verlag).

The code problem for traces---improving the boundaries

Hendrik Jan Hoogeboom, Anca Muscholl

Theoretical Computer Science 172 (1997) Abstract, BibTeX entry, ps.Z File (© Elsevier).

On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's

Juraj Hromkovic, Holger Petersen, Georg Schnitger

Theoretical Computer Science, Volume 410, 2972--2981, 2009.

Regular Ideal Languages and Their Boolean Combinations

Franz Jahn, Manfred Kufleitner, Alexander Lauser

Implementation and Application of Automata (CIAA) 2012, Conference Proceedings, volume 7381 of Lecture Notes in Computer Science, pages 205–216. Springer, 2012.
[arXiv] [© Springer-Verlag]

First-Order Fragments with Successor over Infinite Words

Jakub Kallas, Manfred Kufleitner, Alexander Lauser

Technical Report No. 2010/08, Computer Science, Universität Stuttgart.
[http] [arXiv]

First-order Fragments with Successor over Infinite Words

Jakub Kallas, Manfred Kufleitner, Alexander Lauser

Theoretical Aspects of Computer Science, International Symposium (STACS) 2011, Conference Proceedings, volume 9 of Leibniz International Proceedings in Informatics (LIPIcs), pages 356–367, Schloss Dagstuhl, 2011.
[pdf] [http]

Deciding Whether a Regular Language is Generated by a Splicing System

Lila Kari, Steffen Kopecki

Accepted by DNA 18, 2012.
[arXiv:1112.4897]

On the Regularity of Iterated Hairpin Completion of a Single Word

Lila Kari, Steffen Kopecki, Shinnosuke Seki

On the Regularity of Iterated Hairpin Completion of a Single Word.
In Fundamenta Informaticae, volume 110(1-4), pages 201–215, 2011.
[IOS Press] [arXiv:1104.2385]

Iterated Hairpin Completions of Non-crossing Words

Lila Kari, Steffen Kopecki, Shinnosuke Seki

In M. Bioliková, G. Friedrich, G. Gottlob, S.Katyenbeisser, and G. Turán (editors), 38th Conference on Current Trends in Theorz and Practice of Computer Science, Volume 7147 of LNCS, Pages 337–348, 2011.
[Springer] [arXiv:1110.0760]

On the Iterated Hairpin Completion

Steffen Kopecki

In Y. Gao, H. Lu, S. Seki, and S. Yu (editors), 14th Developments in Language Theory, volume 6224 of LNCS, pages 438-439. Springer, 2010.
[Technical Report] [Poster] [Springer]

On Iterated Hairpin Completion

Steffen Kopecki

In Theoretical Computer Science, Volume 412, Issue 29, Pages 3629–3638, 2011.
[ScienceDirect] [arXiv:1010.3640v3]

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.

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

Manfred Kufleitner

Theoretical Computer Science, 376:89-100, 2007. Special issue DLT 2006.

A Proof of the Factorization Forest Theorem

Manfred Kufleitner

Technical report Nr. 2007/05, Formale Methoden der Informatik, Universität Stuttgart, Germany, 4 pages, October 2007. pdf File

The height of factorization forests

Manfred Kufleitner

In Edward Ochmanski and Jerzy Tyszkiewicz, editors, Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings, volume 5162 of Lecture Notes in Computer Science, pages 443-454. Springer-Verlag, 2008.

On bijective variants of the Burrows-Wheeler transform

Manfred Kufleitner

In Jan Holub and Jan Zdarek, editors, The Prague Stringology Conference 2009, PSC 2009, Prague, Czech Republic, August 31-September 2, 2009, Proceedings, pages 65-79, 2009.

Partially Ordered Two-way Büchi Automata

Manfred Kufleitner, Alexander Lauser

Implementation and Application of Automata (CIAA) 2010, Conference Proceedings, volume 6482 of Lecture Notes in Computer Science, pages 181–190. Springer, 2010.
[pdf] [http] [© Springer-Verlag]

Partially Ordered Two-way Büchi Automata

Manfred Kufleitner, Alexander Lauser

Technical Report No. 2010/03, Computer Science, Universität Stuttgart.
[http] [arXiv]

Partially Ordered Two-way Büchi Automata

Manfred Kufleitner, Alexander Lauser

International Journal of Foundations of Computer Science, Vol. 22(8), World Scientific, 2011
[pdf] [http] [© World Scientific Publishing Company]

Languages of Dot-depth One over Infinite Words

Manfred Kufleitner, Alexander Lauser

IEEE Symposium on Logic in Computer Science (LICS) 2011, Conference Proceedings, pages 23–32. IEEE Computer Society, 2011.
[arXiv]

Around Dot-depth One

Manfred Kufleitner, Alexander Lauser

Technical Report No. 2011/03, Computer Science, University of Stuttgart.
[http] [arXiv]

Cantor Topologies for Finite Words

Manfred Kufleitner, Alexander Lauser

Technical Report No. 2011/02, Computer Science, University of Stuttgart.
[http] [arXiv]

The Join of the Varieties of R-trivial and L-trivial Monoids via Combinatorics on Words

Manfred Kufleitner, Alexander Lauser

Discrete Mathematics & Theoretical Computer Science, 14(1):141-146, 2012.
[arXiv] [pdf] [Artikel bei © Maison de l'Informatique et des Mathématiques Discrètes]

Lattices of Logical Fragments over Words (Extended Abstract)

Manfred Kufleitner, Alexander Lauser

Automata, Languages and Programming, International Colloquium (ICALP) 2012, Conference Proceedings, volume 7392 of Lecture Notes in Computer Science, pages 275–286. Springer, 2012.
[http] [arXiv] [© Springer-Verlag]

Around Dot-Depth One

Manfred Kufleitner, Alexander Lauser

International Journal of Foundations of Computer Science, Vol. 23(6), World Scientific, 2012
[pdf] [http] [© World Scientific Publishing Company]

The Join Levels of the Trotter-Weil Hierarchy are Decidable

Manfred Kufleitner, Alexander Lauser

Mathematical Foundations of Computer Science, International Symposium (MFCS) 2012, Conference Proceedings, volume 7464 of Lecture Notes in Computer Science, pages 603–614. Springer, 2012.
[arXiv] [© Springer-Verlag]

Positive Alternation in FO² Over Finite Words

Manfred Kufleitner, Alexander Lauser

Submitted to Conference on Computer Science Logic 2013 (CSL 2013)

Quantifier Alternation in Two-Variable First-Order Logic with Successor Is Decidable

Manfred Kufleitner, Alexander Lauser

Theoretical Aspects of Computer Science, International Symposium (STACS) 2013, Conference Proceedings, volume 20 of Leibniz International Proceedings in Informatics (LIPIcs), pages 305–316, Schloss Dagstuhl, 2013.
[pdf] [http]

On FO² quantifier alternation over words

Manfred Kufleitner, Pascal Weil

In Rastislav Kralovic and Damian Niwinski, editors, Mathematical Foundations of Computer Science 2009, 34th International Symposium, MFCS 2009, Nový Smokovec, Slovakia, August 24-28, 2009, Proceedings, volume 5734 of Lecture Notes in Computer Science, pages 513-524. Springer-Verlag, 2009.

On the lattice of sub-pseudovarieties of DA

Manfred Kufleitner and Pascal Weil

Semigroup Forum, 81(2):243-254, 2010.

The FO² alternation hierarchy is decidable

Manfred Kufleitner, Pascal Weil

Computer Science Logic (CSL 2012), Conference Proceedings, volume 16 of Leibniz International Proceedings in Informatics (LIPIcs), pages 426–439, Schloss Dagstuhl, 2012.
[pdf] [http]

Efficient Algorithms for highly compressed data: The Word Problem in Generalized Higman Groups is in P

Jürn Laun

Preprint, 2012.
[arXiv:1207.6944v2]

Estimation of the Click Volume by Large Scale Regression Analysis

Yury Lifshits, Dirk Nowotka

NP-completeness results concerning the transformation of logic programs into attribute grammars

Markus Lohrey

Acta Cybernetika 13, S. 209-224, 1998. ps. File.

On the Confluence of Trace Rewriting Systems

Markus Lohrey

FSTTCS 98, LNCS 1530, 319-330, 1998.

Complexity Results for Confluence Problems

Markus Lohrey

Word Problems and Confluence Problems for Restricted Semi-Thue Systems

Markus Lohrey

Confluence Problems for Trace Rewriting Systems

Markus Lohrey

Information and Computation 170, 1-25, 2001.

Word Problems for 2-Homogeneous Monoids and Symmetric Logspace

Markus Lohrey

On the Parallel Complexity of Tree Automata

Markus Lohrey

Safe realizability of high-level message sequence charts

Markus Lohrey

Realizability of high-level message sequence charts: closing the gaps

Markus Lohrey

Automatic structures of bounded degree

Markus Lohrey

Decidability and complexity in automatic monoids

Markus Lohrey

Word problems on compressed words

Markus Lohrey

Word problems and membership problems on compressed words

Markus Lohrey

Implementing Luby's Algorithm on the Cray T3E

Jürgen Gross, Markus Lohrey

Priority and maximal progress are completely axiomatisable (extended abstract)

Holger Hermanns, Markus Lohrey

Axiomatising Divergence

Markus Lohrey, Pedro D'Argenio, Holger Hermanns

On the theory of one-step rewriting in trace monoids

Dietrich Kuske, Markus Lohrey

Decidable theories of Cayley-graphs

Dietrich Kuske, Markus Lohrey

Logical Aspects of Cayley-Graphs: The Group Case

Dietrich Kuske, Markus Lohrey

Decidable first-order theories of one-step rewriting in trace monoids

Dietrich Kuske, Markus Lohrey

First-order and counting theories of omega-automatic structures

Dietrich Kuske, Markus Lohrey

Monadic chain logic over iterations and applications to pushdown systems

Dietrich Kuske, Markus Lohrey

Logical Aspects of Cayley-Graphs: The Monoid Case

Dietrich Kuske, Markus Lohrey

Querying and Embedding Compressed Texts

Yury Lifshits, Markus Lohrey

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

Markus Lohrey, Sebastian Maneth

Bounded MSC communication

Markus Lohrey, Anca Muscholl

Bounded MSC communication

Markus Lohrey, Anca Muscholl

Inverse monoids: decidability and complexity of algebraic questions

Markus Lohrey, Nicole Ondrusch

Theories of HNN-extensions and amalgamated products

Géraud Sénizergues, Markus Lohrey

On the complementation of Büchi asynchronous cellular automata

Anca Muscholl

Theoretical Computer Science 169 (1996) (Preliminary version ICALP'94, LNCS 820) Abstract, BibTeX entry, dvi File, ps.Z File.

Über die Erkennbarkeit unendlicher Spuren

Anca Muscholl

PhDthesis, Institut für Informatik, Universität Stuttgart (1994) Abstract, BibTeX entry, dvi File, ps.Z File.

Matching Specifications for Message Sequence Charts

Anca Muscholl

About the local detection of termination of local computations in graphs

Yves Metivier, Anca Muscholl and Pierre-Andre Wacrenier

Deciding properties for message sequence charts

Anca Muscholl, Doron Peled and Zhendong Su

A Note on the Commutative Closure of Star-Free Languages

Anca Muscholl, Holger Petersen

Height-Deterministic Pushdown Automata

Dirk Nowotka, Jiri Srba

Some results concerning two-dimensional Turing machines and finite automata

Holger Petersen

Alternation in simple devices

Holger Petersen

The Computation of Partial Recursive Word-Functions Without Read-Instructions

Holger Petersen

Mathematical Logic Quarterly, 42 (1996) 312-318.

The power of programs with restricted control structure

Holger Petersen

Preproceedings of WCCL'96, Preprint-Reihe Mathematik - Nr. 1 - 1996, Ernst-Moritz-Arndt-Universität Greifswald, 56-58. ps.gz File.

A Census Technique for Simple Computing Devices

Holger Petersen

Report 1997/07, Universität Stuttgart, Fakultät Informatik.

The Equivalence of Pebbles and Sensing Heads for Finite Automata

Holger Petersen

Proc. 11th FCT, Springer, LNCS 1279 (1997), 400--410.

Homomorphic Images of Sentential Forms and Terminating Grammars

Holger Petersen

Proc. 22nd MFCS, Springer, LNCS 1295 (1997), 448--457.

Separation Results for Rebound Automata

Holger Petersen

MFCS 2000, LNCS 1893, 589--598, 2000.

Survey of Decision Problems for Regular Expressions

Holger Petersen

Proc. AFL'02, 10th International Conference on Automata and Formal Languages, Debrecen, 2002.

Bounds for the Element Distinctness Problem on One-Tape Turing Machines

Holger Petersen

IPL, Volume 81, 75--79, 2002.

The Membership Problem for Regular Expressions with Intersection is Complet e in LOG-CFL

Holger Petersen

Proc. STACS'02, Juan les Pins, Springer, LNCS 2285, 513--522, 2002.

Element Distinctness on One-Tape Turing Machines

Omer Berkman, Amir M. Ben-Amram, Holger Petersen

Acta Informatica, Volume 40, 81--94, 2003.

A Note on Rebound Turing Machines

Katsushi Inoue, Akira Ito, Takashi Kamiura, Holger Petersen, Lan Zhang

Technical Report of IEICE, COMP2003-27, 25--32, 2003.

Complexity Results for Prefix Grammars

Markus Lohrey, Holger Petersen

R.A.I.R.O. Informatique Theorique et Applications, Volume 39, 391--401, 2005.

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.

String Matching with Simple Devices

Holger Petersen

IPL 105 (2007), 32 -- 34.

Element distinctness and sorting on one-tape off-line Turing machines

Holger Petersen

Proc. 34th International Conference on Current Trends in Theory and Practice of Computer Science, LNCS 4910 (2008), 406 -- 417.

Improved bounds for range mode and range median queries

Holger Petersen

Proc. 34th International Conference on Current Trends in Theory and Practice of Computer Science, LNCS~4910 (2008), 418 -- 423.

Simulations by Time-Bounded Counter Machines

Holger Petersen

Proc. DLT 2009, Springer, LNCS 5583 (2009), 410--418.

Range Mode and Range Median Queries in Constant Time and Sub-Quadratic Space

Holger Petersen, Szymon Grabowski

IPL, Volume 109, 225--228, 2009.

Counting and empty alternating pushdown automata

Klaus Reinhardt

In 7th IMYCS, Smolenice Castle, Tschechoslowakei, 1992.

Sorting in-place with a worst case complexity of n log n - 1.3 n + o(log n) comparisons and epsilon n log n+ o(1) transports

Klaus Reinhardt

In Proceedings of the 3rd ISAAC 92, 1992. LNCS 650, 1992.

Abteilung Theoretische Informatik

Veröffentlichungen / Publications

A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time

E. Allender, R. Beigel, U. Hertrampf, S. Homer

Almost-everywhere Complexity Hierarchies for Nondeterministic Time

E. Allender, R. Beigel, U. Hertrampf, S. Homer

On the Power of Uniform Families of Constant Depth Threshold Circuits

E. Allender, U. Hertrampf

Depth Reduction for Circuits of Unbounded Fan-In

E. Allender, U. Hertrampf

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: Special Issue, 2010.

Sergei Artemov, Volker Diekert, Dima Grigoriev (editors)

Theory of Computing Systems: Special Issue, 2010.

Sergei Artemov, Volker Diekert, Alexander Razborov (editors)

A Structural Property of Regular Frequency Computations

Holger Austinat, Volker Diekert, Ulrich Hertrampf

Regular Frequency Computations

Holger Austinat, Volker Diekert, Ulrich Hertrampf, Holger Petersen

Structure and Importance of Logspace-MOD-Classes

G. Buntrock, C. Damm, U. Hertrampf, C. Meinel

Counting Classes: Thresholds, Parity, Mods, and Fewness

R. Beigel, J. Gill, U. Hertrampf

Efficient rewriting in cograph trace monoids

Michael Bertol

On efficient reduction-algorithms for some trace rewriting systems

Michael Bertol, Volker Diekert

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

Michael Bertol, Volker Diekert

Nonfinite Aximatizability of the Equational Theory of Shuffle

Zoltán Ésik, Michael Bertol

The Tautologies over a finite set are context-free

Michael Bertol, Klaus Reinhardt

Classification tree sources

Edgar Binder and Manfred Kufleitner

Combining models in data compression

Manfred Kufleitner, Edgar Binder, Alexander Fries

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

Ronald V. Book, Volker Diekert

The Chain Method to Separate Counting Classes.

K. Cronauer, U. Hertrampf, H. Vollmer, K.W. Wagner

Partnerschaftsvermittlung

Volker Claus, Volker Diekert, Holger Petersen

Marriage Broker

Volker Claus, Volker Diekert, Holger Petersen

Rankers over Infinite Words (Extended Abstract)

Luc Dartois, Manfred Kufleitner, Alexander Lauser

Rankers over Infinite Words

Luc Dartois, Manfred Kufleitner, Alexander Lauser

Research topics in the theory of free partially commutative monoids

Volker Diekert

Combinatorics on Traces

Volker Diekert

Combinatorial rewriting on traces

Volker Diekert

Word problems over traces which are solvable in linear time

Volker Diekert

On the concatenation of infinite traces

Volker Diekert

Möbius functions and confluent semi-commutations

Volker Diekert

Rewriting, semi-commutations, and Möbius functions

Volker Diekert

Complex and complex-like traces

Volker Diekert

A partial trace semantics for Petri nets

Volker Diekert

A Remark on Trace Equations

Volker Diekert

A Pure Future Local Temporal Logic Beyond Cograph-Monoids

Volker Diekert

Makanin's Algorithm

Volker Diekert

Characterization of the expressive power of silent transitions in timed automata

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

Geodesic rewriting systems and pregroups

Volker Diekert, Andrew J. Duncan and Alexei Miasnikov

Cyclic rewriting and conjugacy problems

Volker Diekert, Andrew Duncan, Alexei G. Myasnikov