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

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]

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]

Deciding Whether a Regular Language is Generated by a Splicing System

Lila Kari, Steffen Kopecki

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

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 Theory and Practice of Computer Science, Volume 7147 of LNCS, Pages 337–348, 2011.
[Springer] [arXiv:1110.0760]

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]

The FO2 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]