Denis Thérien

Kristoffer Arnsfelt Hansen

Theory Comput. Syst., 2014

2011

The Power of Diversity.

[BibT_eX]

[DOI]

Proceedings of the Descriptional Complexity of Formal Systems, 2011

2010

Weakly Iterated Block Products and Applications to Logic and Complexity.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 2010

10061 Executive Summary - Circuits, Logic, and Games.

[BibT_eX]

[DOI]

Proceedings of the Circuits, Logic, and Games, 07.02. - 12.02.2010, 2010

10061 Abstracts Collection - Circuits, Logic, and Games.

[BibT_eX]

[DOI]

Proceedings of the Circuits, Logic, and Games, 07.02. - 12.02.2010, 2010

2009

An Algebraic Perspective on Boolean Function Learning.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 20th International Conference, 2009

2008

Modular quantifiers.

[BibT_eX]

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

2007

Logic Meets Algebra: the Case of Regular Languages.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2007

2006

A Note on MODp - MODm Circuits.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2006

Algebraic Results on Quantum Automata.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2006

The many faces of a translation.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2006

Learning expressions and programs over monoids.

[BibT_eX]

[DOI]

Inf. Comput., 2006

Languages with Bounded Multiparty Communication Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Bridges between Algebraic Automata Theory and Complexity Theory.

[BibT_eX]

Bull. EATCS, 2006

Lower bounds for circuits with MOD_m gates.

[BibT_eX]

[DOI]

Navin Goyal

Pavel Pudlák

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

06451 Abstracts Collection -- Circuits, Logic, and Games .

[BibT_eX]

[DOI]

Heribert Vollmer

Proceedings of the Circuits, Logic, and Games, 08.11. - 10.11.2006, 2006

06451 Executive Summary -- Circuits, Logic, and Games .

[BibT_eX]

[DOI]

Heribert Vollmer

Proceedings of the Circuits, Logic, and Games, 08.11. - 10.11.2006, 2006

An Algebraic Point of View on the Crane Beach Property.

[BibT_eX]

[DOI]

Clemens Lautemann

Proceedings of the Computer Science Logic, 20th International Workshop, 2006

Circuit Lower Bounds via Ehrenfeucht-Fraisse Games.

[BibT_eX]

[DOI]

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Complete Classifications for the Communication Complexity of Regular Languages.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2005

First-order expressibility of languages with neutral letters or: The Crane Beach conjecture.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2005

Imre Simon: an exceptional graduate student.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2005

The dot-depth and the polynomial hierarchies correspond on the delta levels.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2005

Tractable Clones of Polynomials over Semigroups

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Bounded-depth circuits: separating wires from gates.

[BibT_eX]

[DOI]

Michal Koucký

Pavel Pudlák

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Restricted Two-Variable Sentences, Circuits and Communication Complexity.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Groupoids That Recognize Only Regular Languages.

[BibT_eX]

[DOI]

François Lemieux

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004

Nesting Until and Since in Linear Temporal Logic.

[BibT_eX]

[DOI]

Thomas Wilke

Theory Comput. Syst., 2004

Monoids and Computations.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 2004

Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups

[BibT_eX]

[DOI]

Ondrej Klíma

Electron. Colloquium Comput. Complex., 2004

Regular Languages, Unambiguous Concatenation and Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

The Dot-Depth and the Polynomial Hierarchy Correspond on the Delta Levels.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 2004

2003

Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2003

An algebraic approach to data languages and timed languages.

[BibT_eX]

[DOI]

Patricia Bouyer

Antoine Petit

Inf. Comput., 2003

Algebraic Characterizations of Small Classes of Boolean Functions.

[BibT_eX]

[DOI]

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Locally Commutative Categories.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

2002

Weakly Iterated Block Products of Finite Monoids.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2002: Theoretical Informatics, 2002

2001

Temporal Logic and Semidirect Products: An Effective Characterization of the Until Hierarchy.

[BibT_eX]

[DOI]

Thomas Wilke

SIAM J. Comput., 2001

On the Languages Recognized by Nilpotent Groups (a translation of "Sur les Langages Reconnus par des Groupes Nilpotents")

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

The Computing Power of Programs over Finite Monoids

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

Learning Expressions over Monoids.

[BibT_eX]

[DOI]

Proceedings of the STACS 2001, 2001

Star-Free Open Languages and Aperiodic Loops.

[BibT_eX]

[DOI]

François Lemieux

Proceedings of the STACS 2001, 2001

Satisfiability of Systems of Equations over Finite Monoids.

[BibT_eX]

[DOI]

Cristopher Moore

Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

The Crane Beach Conjecture.

[BibT_eX]

[DOI]

Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001

Partially-Ordered Two-Way Automata: A New Characterization of DA.

[BibT_eX]

[DOI]

Heribert Vollmer

Proceedings of the Developments in Language Theory, 5th International Conference, 2001

An Algebraic Characterization of Data and Timed Languages.

[BibT_eX]

[DOI]

Patricia Bouyer

Antoine Petit

Proceedings of the CONCUR 2001, 2001

2000

Programs over semigroups of dot-depth one.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

Circuits and Expressions with Nonassociative Gates.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2000

An ergodic theorem for read-once non-uniform deterministic finite automata.

[BibT_eX]

[DOI]

Mikael Goldmann

Alexander Russell

Inf. Process. Lett., 2000

Equation Satisfiability and Program Satisfiability for Finite Monoids.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

1999

Efficient Threshold Circuits for Power Series.

[BibT_eX]

[DOI]

Inf. Comput., 1999

Modular Temporal Logic.

[BibT_eX]

[DOI]

Augustin Baziramwabo

Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, 1999

1998

Nondeterministic NC1 Computation.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1998

Threshold Circuits of Small Majority-Depth.

[BibT_eX]

[DOI]

Inf. Comput., 1998

Over Words, Two Variables Are as Powerful as One Quantifier Alternation.

[BibT_eX]

[DOI]

Thomas Wilke

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

An Algebraic Approach to Communication Complexity.

[BibT_eX]

[DOI]

Jean-François Raymond

Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

1997

Finite Semigroup Varieties Defined by Programs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1997

Finite Moniods: From Word to Circuit Evaluation.

[BibT_eX]

[DOI]

SIAM J. Comput., 1997

Finite Loops Recognize Exactly the Regular Open Languages.

[BibT_eX]

[DOI]

François Lemieux

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

Circuits and Expressions with NOn-Associative Gates.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996

Logspace and Logtime Leaf Languages.

[BibT_eX]

[DOI]

Birgit Jenner

Inf. Comput., 1996

Nondeterministic NC1 Computation.

[BibT_eX]

[DOI]

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995

Regular Languages Defined with Generalized Quanifiers

[BibT_eX]

[DOI]

Wolfgang Thomas

Inf. Comput., May, 1995

1994

Circuits Constructed with Mod_q Gates Cannot Compute "And" in Sublinear Size.

[BibT_eX]

[DOI]

Comput. Complex., 1994

Special Issue on Circuit Complexity: Foreword.

[BibT_eX]

[DOI]

Comput. Complex., 1994

Logics For Context-Free Languages.

[BibT_eX]

[DOI]

Clemens Lautemann

Proceedings of the Computer Science Logic, 8th International Workshop, 1994

1993

The Bideterministic Concatenation Product.

[BibT_eX]

[DOI]

Jean-Eric Pin

Int. J. Algebra Comput., 1993

Threshold Circuits for Iterated Multiplication: Using AC0 for Free.

[BibT_eX]

[DOI]

Proceedings of the STACS 93, 1993

1992

Some Results on the Generalized Star-Height Problem

[BibT_eX]

[DOI]

Jean-Eric Pin

Inf. Comput., December, 1992

Regular Languages in NC¹.

[BibT_eX]

[DOI]

Kevin J. Compton

J. Comput. Syst. Sci., 1992

The Membership Problem in Aperiodic Transformation Monoids.

[BibT_eX]

[DOI]

J. ACM, 1992

Circuits Constructed with MODq Gates Cannot Compute AND in Sublinear Size.

[BibT_eX]

[DOI]

Proceedings of the LATIN '92, 1992

1991

NC¹: The Automata-Theoretic Viewpoint.

[BibT_eX]

[DOI]

Comput. Complex., 1991

1990

Non-Uniform Automata Over Groups

[BibT_eX]

[DOI]

Inf. Comput., December, 1990

1989

Programs over Aperiodic Monoids.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1989

New Results on the Generalized Star-Height Problem.

[BibT_eX]

[DOI]

Jean-Eric Pin

Proceedings of the STACS 89, 1989

Testing Membership: Beyond Permutation Groups (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the STACS 89, 1989

Automata Theory Meets Circuit Complexity.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

1988

Finite monoids and the fine structure of NC1.

[BibT_eX]

[DOI]

J. ACM, 1988

Categories Et Langages De Dot-Depth Un.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1988

Finite automata and computational complexity.

[BibT_eX]

[DOI]

Proceedings of the Formal Properties of Finite Automata and Applications, 1988

regular Languages Defined with Generalized Quantifiers.

[BibT_eX]

[DOI]

Wolfgang Thomas

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

1987

Finite Monoids and the Fine Structure of NC¹

[BibT_eX]

[DOI]

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Non-Uniform Automata Over Groups.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

1986

Varieties of Finite Categories.

[BibT_eX]

[DOI]

Alex Weiss

RAIRO Theor. Informatics Appl., 1986

1981

Classification of Finite Monoids: The Language Approach.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1981

1979

Languages of Nilpotent and Solvable Groups (Extended Abstract).

[BibT_eX]

[DOI]