Volker Diekert

Mikhail Volkov

Theory Comput. Syst., June, 2024

2022

Regular matching problems for infinite trees.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2022

Properties of graphs specified by a regular language.

[BibT_eX]

[DOI]

Henning Fernau

Petra Wolf

Acta Informatica, 2022

Reachability Games and Parity Games.

[BibT_eX]

[DOI]

Proceedings of the Theoretical Aspects of Computing - ICTAC 2022, 2022

2020

Solutions to twisted word equations and equations in virtually free groups.

[BibT_eX]

[DOI]

Murray Elder

Int. J. Algebra Comput., 2020

Decidability of membership problems for flat rational subsets of GL(2, Q) and singular matrices.

[BibT_eX]

[DOI]

Igor Potapov

Pavel Semukhin

Proceedings of the ISSAC '20: International Symposium on Symbolic and Algebraic Computation, 2020

2019

Algorithmic Problems in Group Theory (Dagstuhl Seminar 19131).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2019

2017

Equations Over Free Inverse Monoids with Idempotent Variables.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2017

Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem.

[BibT_eX]

[DOI]

J. Symb. Comput., 2017

Characterizing classes of regular languages using prefix codes of bounded synchronization delay.

[BibT_eX]

[DOI]

Tobias Walter

Int. J. Algebra Comput., 2017

Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups.

[BibT_eX]

[DOI]

Murray Elder

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Church-Rosser Systems, Codes with Bounded Synchronization Delay and Local Rees Extensions.

[BibT_eX]

[DOI]

Lukas Fleischer

Proceedings of the Combinatorics on Words - 11th International Conference, 2017

2016

A survey on the local divisor technique.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

QuickHeapsort: Modifications and Improved Analysis.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2016

Logspace computations in graph products.

[BibT_eX]

[DOI]

Jonathan Kausch

J. Symb. Comput., 2016

Solution sets for equations over free groups are EDT0L languages.

[BibT_eX]

[DOI]

Laura Ciobanu

Murray Elder

Int. J. Algebra Comput., 2016

Finding all solutions of equations in free groups and monoids with involution.

[BibT_eX]

[DOI]

Artur Jez

Wojciech Plandowski

Inf. Comput., 2016

Conjugacy in Baumslag's Group, Generic Case Complexity, and Division in Power Circuits.

[BibT_eX]

[DOI]

Algorithmica, 2016

Solutions of Word Equations Over Partially Commutative Structures.

[BibT_eX]

[DOI]

Artur Jez

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Discrete Algebraic Methods - Arithmetic, Cryptography, Automata and Groups.

[BibT_eX]

[DOI]

de Gruyter, ISBN: 978-3-11-041332-8, 2016

2015

Omega-Rational Expressions with Bounded Synchronization Delay.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2015

Regular Languages Are Church-Rosser Congruential.

[BibT_eX]

[DOI]

J. ACM, 2015

SLP compression for solutions of equations with constraints in free and hyperbolic groups.

[BibT_eX]

[DOI]

Atefeh Mohajeri Moghaddam

Olga Kharlampovich

Int. J. Algebra Comput., 2015

Asymptotic Approximation for the Quotient Complexities of Atoms.

[BibT_eX]

[DOI]

Tobias Walter

Acta Cybern., 2015

A Note on Monitors and Büchi Automata.

[BibT_eX]

[DOI]

Igor Walukiewicz

Proceedings of the Theoretical Aspects of Computing - ICTAC 2015, 2015

More Than 1700 Years of Word Equations.

[BibT_eX]

[DOI]

Proceedings of the Algebraic Informatics - 6th International Conference, 2015

2014

Topology, monitorable properties and runtime verification.

[BibT_eX]

[DOI]

Martin Leucker

Theor. Comput. Sci., 2014

2013

Context-Free Groups and their Structure Trees.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 2013

Elemente der diskreten Mathematik - Zahlen und Zählen, Graphen und Verbände.

[BibT_eX]

[DOI]

Gerhard Rosenberger

De Gruyter Studium, de Gruyter, ISBN: 978-3-11-027767-8, 2013

Diskrete algebraische Methoden - Arithmetik, Kryptographie, Automaten und Gruppen.

[BibT_eX]

[DOI]

Gerhard Rosenberger

De Gruyter Studium, de Gruyter, ISBN: 978-3-11-031260-7, 2013

2012

Star-free languages are Church-Rosser congruential.

[BibT_eX]

[DOI]

Pascal Weil

Theor. Comput. Sci., 2012

Language theoretical properties of hairpin formations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2012

Group Extensions over Infinite Words.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2012

Efficient Algorithms for Highly Compressed Data: the Word Problem in Higman's Group is in P.

[BibT_eX]

[DOI]

Jürn Laun

Alexander Ushakov

Int. J. Algebra Comput., 2012

Deciding regularity of hairpin completions of regular languages in polynomial time.

[BibT_eX]

[DOI]

Victor Mitrana

Inf. Comput., 2012

Cyclic rewriting and conjugacy problems.

[BibT_eX]

[DOI]

Andrew J. Duncan

Groups Complex. Cryptol., 2012

The Krohn-Rhodes Theorem and Local Divisors.

[BibT_eX]

[DOI]

Benjamin Steinberg

Fundam. Informaticae, 2012

On Distributed Monitoring of Asynchronous Systems.

[BibT_eX]

[DOI]

Proceedings of the Logic, Language, Information and Computation, 2012

Logspace Computations in Graph Groups and Coxeter Groups.

[BibT_eX]

[DOI]

Jonathan Kausch

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

Bounded Synchronization Delay in Omega-Rational Expressions.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2012

2011

Trace Theory.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Parallel Computing, 2011

Fragments of First-Order Logic over Infinite Words.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

Preface.

[BibT_eX]

[DOI]

Dirk Nowotka

Int. J. Found. Comput. Sci., 2011

It is NL-Complete to Decide Whether a Hairpin Completion of Regular Languages is Regular.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2011

On Computing Geodesics in Baumslag-Solitar Groups.

[BibT_eX]

[DOI]

Jürn Laun

Int. J. Algebra Comput., 2011

Solving Word Problems in Group Extensions over Infinite Words.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 15th International Conference, 2011

Marriage Broker.

[BibT_eX]

[DOI]

Volker Claus

Holger Petersen

Proceedings of the Algorithms Unplugged, 2011

2010

Preface.

[BibT_eX]

[DOI]

Sergei N. Artëmov

Alexander A. Razborov

Theory Comput. Syst., 2010

Preface.

[BibT_eX]

[DOI]

Sergei N. Artëmov

Dima Grigoriev

Theory Comput. Syst., 2010

Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2010

2009

Some remarks about stabilizers.

[BibT_eX]

[DOI]

Dalia Krieger

Theor. Comput. Sci., 2009

On the Hairpin Completion of Regular Languages.

[BibT_eX]

[DOI]

Victor Mitrana

Proceedings of the Theoretical Aspects of Computing, 2009

2008

Partnerschaftsvermittlung.

[BibT_eX]

[DOI]

Volker Claus

Holger Petersen

Proceedings of the Taschenbuch der Algorithmen, 2008

Foreword.

[BibT_eX]

[DOI]

Sergei N. Artëmov

Dima Grigoriev

Theory Comput. Syst., 2008

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

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2008

Algorithmic Problems on Inverse Monoids over Virtually Free Groups.

[BibT_eX]

[DOI]

Nicole Ondrusch

Int. J. Algebra Comput., 2008

Word Equations over Graph Products.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 2008

First-order definable languages.

[BibT_eX]

Proceedings of the Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]., 2008

2007

Foreword.

[BibT_eX]

[DOI]

Bruno Durand

Theory Comput. Syst., 2007

On First-Order Fragments for Mazurkiewicz Traces.

[BibT_eX]

[DOI]

Martin Horsch

Fundam. Informaticae, 2007

Equations: From Words to Graph Products.

[BibT_eX]

Proceedings of the LATA 2007. Proceedings of the 1st International Conference on Language and Automata Theory and Applications., 2007

On First-Order Fragments for Words and Mazurkiewicz Traces.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 11th International Conference, 2007

2006

From local to global temporal logics over Mazurkiewicz traces.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2006

Foreword.

[BibT_eX]

[DOI]

Michel Habib

Theory Comput. Syst., 2006

Solvability of Equations in Graph Groups Is Decidable.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 2006

Pure future local temporal logics are expressively complete for Mazurkiewicz traces.

[BibT_eX]

[DOI]

Inf. Comput., 2006

Partially Commutative Inverse Monoids.

[BibT_eX]

[DOI]

Alexander Miller

Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

2005

Regular frequency computations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

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

[BibT_eX]

[DOI]

Claudio Gutierrez

Christian Hagenah

Inf. Comput., 2005

2004

Existential and Positive Theories of Equations in Graph Products.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2004

Local temporal logic is expressively complete for cograph dependence alphabets.

[BibT_eX]

[DOI]

Inf. Comput., 2004

2003

A structural property of regular frequency computations.

[BibT_eX]

[DOI]

Holger Austinat

Ulrich Hertrampf

Theor. Comput. Sci., 2003

2002

LTL Is Expressively Complete for Mazurkiewicz Traces.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2002

A Note on The Existential Theory of Equations in Plain Groups.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 2002

A Remark about Quadratic Trace Equations.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 6th International Conference, 2002

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

[BibT_eX]

[DOI]

Proceedings of the Formal and Natural Computing, 2002

2001

Solvability of Equations in Free Partially Commutative Groups Is Decidable.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

1999

Solving Word Equations modulo Partial Commutations.

[BibT_eX]

[DOI]

Yuri V. Matiyasevich

Theor. Comput. Sci., 1999

On Quadratic Word Equations.

[BibT_eX]

[DOI]

John Michael Robson

Proceedings of the STACS 99, 1999

An Expressively Complete Temporal Logic without Past Tense Operators for Mazurkiewicz Traces.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 13th International Workshop, 1999

1998

Characterization of the Expressive Power of Silent Transitions in Timed Automata.

[BibT_eX]

[DOI]

Fundam. Informaticae, 1998

Approximating Traces.

[BibT_eX]

[DOI]

Acta Informatica, 1998

1997

Partial Commutation and Traces.

[BibT_eX]

[DOI]

Yves Métivier

Proceedings of the Handbook of Formal Languages, Volume 3: Beyond Words., 1997

Removing epsilon-Transitions in Timed Automata.

[BibT_eX]

[DOI]

Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

Solving Trace Equations Using Lexicographical Normal Forms.

[BibT_eX]

[DOI]

Yuri V. Matiyasevich

Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

A Remark on Trace Equations.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Computer Science: Potential - Theory, 1997

1996

A Note on Métivier's Construction of Asynchronous Automata for Triangulated Graphs.

[BibT_eX]

[DOI]

Fundam. Informaticae, 1996

Trace Rewriting: Computing Normal Forms in Time O(n log n).

[BibT_eX]

[DOI]

Michael Bertol

Proceedings of the STACS 96, 1996

Code Problems on Traces.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1996, 1996

1995

Rational and Recognizable Complex Trace Languages

[BibT_eX]

[DOI]

Inf. Comput., January, 1995

On Confluence of One-Rule Trace-Rewriting Systems.

[BibT_eX]

[DOI]

Celia Wrathall

Math. Syst. Theory, 1995

On Codings of Traces.

[BibT_eX]

[DOI]

Klaus Reinhardt

Proceedings of the STACS 95, 1995

A Domain for Concurrent Termination: A Generalization of Mazurkiewicz Traces (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Recent Developments in Trace Theory.

[BibT_eX]

Proceedings of the Developments in Language Theory II, 1995

Construction of Asynchronous Automata.

[BibT_eX]

[DOI]

Proceedings of the Book of Traces, 1995

1994

On Confluent Semi-commutations: Decidability and Complexity Results

[BibT_eX]

[DOI]

Edward Ochmanski

Klaus Reinhardt

Inf. Comput., April, 1994

A Partial Trace Semantics for Petri Nets.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1994

Deterministic Asynchronous Automata for Infinite Traces.

[BibT_eX]

[DOI]

Acta Informatica, 1994

1993

On the Concentration of Infinite Traces.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1993

Möbius Functions and Confluent Semi-Commutations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1993

Complex and Complex-Like Traces.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1993, 1993

Rewriting, Möbius Functions and Semi-Commutations.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 9th International Symposium, 1993

On Efficient Reduction Algorithms for Some Trace Rewriting Systems.

[BibT_eX]

[DOI]

Michael Bertol

Proceedings of the Term Rewriting, 1993

1992

One-Rule Trace-Rewriting Systems and Confluence.

[BibT_eX]

[DOI]

Celia Wrathall

Friedrich Otto

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

1991

On "Inherently Context-Sensitive" Languages - An Application of Complexity Cores.

[BibT_eX]

[DOI]

Ronald V. Book

Inf. Process. Lett., 1991

On the Concatenation of Infinite Traces.

[BibT_eX]

[DOI]

Proceedings of the STACS 91, 1991

Recognizable Complex Trace Languages.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1991, 1991

1990

Two contributions to the theory of Marzukiewicz traces

[BibT_eX]

[DOI]

Forschungsberichte, TU Munich, 1990

Word Problems Over Traces which are Solvable in Linear Time.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1990

Combinatorial Rewriting on Traces.

[BibT_eX]

[DOI]

Proceedings of the STACS 90, 1990

Combinatorics on Traces

[BibT_eX]

[DOI]

Lecture Notes in Computer Science 454, Springer, ISBN: 3-540-53031-2, 1990

1989

On the Knuth-Bendix Completion for Concurrent Processes.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1989

On the Synchronization of Traces.

[BibT_eX]

[DOI]

Walter Vogler

Math. Syst. Theory, 1989

Hotz-Isomorphism Theorems In Formal Language Theory.

[BibT_eX]

[DOI]

Axel Möbus

RAIRO Theor. Informatics Appl., 1989

1988

Local Checking of Trace Synchroniziability.

[BibT_eX]

[DOI]

Walter Vogler

Proceedings of the Mathematical Foundations of Computer Science 1988, 1988

Transitive Orientations, Möbius Functions, and Complete Semi-Thue Systems for Free Partially Commutative Monoids.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

1987

Some Remarks on Presentations by Finite Church-Rosser Thue Systems.

[BibT_eX]

[DOI]

Proceedings of the STACS 87, 1987

1986

Commutative monoids have complete presentations by free (non-commutative) monoids.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1986

On some variants of the Ehrenfeucht conjecture.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1986

Complete Semi-Thue Systems for Abelian Groups.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1986

Investigations on Hotz Groups for Arbitrary Grammars.

[BibT_eX]

[DOI]

Acta Informatica, 1986

1985

On Hotz Groups and Homomorphic Images of Sentential Form Languages.

[BibT_eX]

[DOI]