Denis Thérien

Arkadev Chattopadhyay, Ricard Gavaldà, Kristoffer Arnsfelt Hansen, Denis Thérien: Learning Read-Constant Polynomials of Constant Degree Modulo Composites. CSR 2011: 29-42

Denis Thérien: The Power of Diversity. DCFS 2011: 43-54

Howard Straubing, Pascal Tesson, Denis Thérien: Weakly Iterated Block Products and Applications to Logic and Complexity. IJAC 20(2): 319-341 (2010)

Ricard Gavaldà, Denis Thérien: An Algebraic Perspective on Boolean Function Learning. ALT 2009: 201-215

Howard Straubing, Denis Thérien: Modular quantifiers. Logic and Automata 2008: 613-628

Pascal Tesson, Denis Thérien: Logic Meets Algebra: the Case of Regular Languages. Logical Methods in Computer Science 3(1) (2007)

Ondrej Klíma, Pascal Tesson, Denis Thérien: Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups. Theory Comput. Syst. 40(3): 263-297 (2007)

Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien: Languages with Bounded Multiparty Communication Complexity. STACS 2007: 500-511

Thomas Schwentick, Denis Thérien, Heribert Vollmer (Eds.): Circuits, Logic, and Games, 08.11. - 10.11.2006. Dagstuhl Seminar Proceedings 06451, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2007

Pascal Tesson, Denis Thérien: Logic Meets Algebra: the Case of Regular Languages. CoRR abs/cs/0701154 (2007)

Pascal Tesson, Denis Thérien: Bridges between Algebraic Automata Theory and Complexity Theory. Bulletin of the EATCS 88: 37-64 (2006)

Ricard Gavaldà, Pascal Tesson, Denis Thérien: Learning expressions and programs over monoids. Inf. Comput. 204(2): 177-209 (2006)

Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer: The many faces of a translation. J. Comput. Syst. Sci. 72(1): 163-179 (2006)

Andris Ambainis, Martin Beaudry, Marats Golovkins, Arnolds Kikusts, Mark Mercer, Denis Thérien: Algebraic Results on Quantum Automata. Theory Comput. Syst. 39(1): 165-188 (2006)

Howard Straubing, Denis Thérien: A Note on MOD_p - MOD_m Circuits. Theory Comput. Syst. 39(5): 699-706 (2006)

Michal Koucký, Clemens Lautemann, Sebastian Poloczek, Denis Thérien: Circuit Lower Bounds via Ehrenfeucht-Fraisse Games. IEEE Conference on Computational Complexity 2006: 190-201

Clemens Lautemann, Pascal Tesson, Denis Thérien: An Algebraic Point of View on the Crane Beach Property. CSL 2006: 426-440

Thomas Schwentick, Denis Thérien, Heribert Vollmer: 06451 Executive Summary -- Circuits, Logic, and Games . Circuits, Logic, and Games 2006

Thomas Schwentick, Denis Thérien, Heribert Vollmer: 06451 Abstracts Collection -- Circuits, Logic, and Games . Circuits, Logic, and Games 2006

Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlák, Denis Thérien: Lower bounds for circuits with MOD_m gates. FOCS 2006: 709-718

Arkadev Chattopadhyay, Michal Koucký, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien: Languages with Bounded Multiparty Communication Complexity. Electronic Colloquium on Computational Complexity (ECCC) 13(117) (2006)

Bernd Borchert, Klaus-Jörn Lange, Frank Stephan, Pascal Tesson, Denis Thérien: The dot-depth and the polynomial hierarchies correspond on the delta levels. Int. J. Found. Comput. Sci. 16(4): 625-644 (2005)

Denis Thérien: Imre Simon: an exceptional graduate student. ITA 39(1): 297-304 (2005)

David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, Denis Thérien: First-order expressibility of languages with neutral letters or: The Crane Beach conjecture. J. Comput. Syst. Sci. 70(2): 101-127 (2005)

Pascal Tesson, Denis Thérien: Complete Classifications for the Communication Complexity of Regular Languages. Theory Comput. Syst. 38(2): 135-159 (2005)

Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien: Tractable Clones of Polynomials over Semigroups. CP 2005: 196-210

Martin Beaudry, François Lemieux, Denis Thérien: Groupoids That Recognize Only Regular Languages. ICALP 2005: 421-433

Pascal Tesson, Denis Thérien: Restricted Two-Variable Sentences, Circuits and Communication Complexity. ICALP 2005: 526-538

Michal Koucký, Pavel Pudlák, Denis Thérien: Bounded-depth circuits: separating wires from gates. STOC 2005: 257-265

Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien: Tractable Clones of Polynomials over Semigroups. Electronic Colloquium on Computational Complexity (ECCC)(059) (2005)

Pascal Tesson, Denis Thérien: Monoids and Computations. IJAC 14(5-6): 801-816 (2004)

Denis Thérien, Thomas Wilke: Nesting Until and Since in Linear Temporal Logic. Theory Comput. Syst. 37(1): 111-131 (2004)

Bernd Borchert, Klaus-Jörn Lange, Frank Stephan, Pascal Tesson, Denis Thérien: The Dot-Depth and the Polynomial Hierarchy Correspond on the Delta Levels. Developments in Language Theory 2004: 89-101

Denis Thérien: Regular Languages, Unambiguous Concatenation and Computational Complexity. FSTTCS 2004: 49-57

Andris Ambainis, Martin Beaudry, Marats Golovkins, Arnolds Kikusts, Mark Mercer, Denis Thérien: Algebraic Results on Quantum Automata. STACS 2004: 93-104

Ondrej Klíma, Pascal Tesson, Denis Thérien: Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups. Electronic Colloquium on Computational Complexity (ECCC)(091) (2004)

Patricia Bouyer, Antoine Petit, Denis Thérien: An algebraic approach to data languages and timed languages. Inf. Comput. 182(2): 137-162 (2003)

Howard Straubing, Denis Thérien: Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables. Theory Comput. Syst. 36(1): 29-69 (2003)

Arkadev Chattopadhyay, Denis Thérien: Locally Commutative Categories. ICALP 2003: 984-995

Pascal Tesson, Denis Thérien: Complete Classifications for the Communication Complexity of Regular Languages. STACS 2003: 62-73

Ricard Gavaldà, Denis Thérien: Algebraic Characterizations of Small Classes of Boolean Functions. STACS 2003: 331-342

Pascal Tesson, Denis Thérien: The Computing Power of Programs over Finite Monoids. Journal of Automata, Languages and Combinatorics 7(2): 247-258 (2002)

Howard Straubing, Denis Thérien: Weakly Iterated Block Products of Finite Monoids. LATIN 2002: 91-104

Denis Thérien, Thomas Wilke: Nesting Until and Since in Linear Temporal Logic. STACS 2002: 455-464

Denis Thérien, Thomas Wilke: Temporal Logic and Semidirect Products: An Effective Characterization of the Until Hierarchy. SIAM J. Comput. 31(3): 777-798 (2001)

Patricia Bouyer, Antoine Petit, Denis Thérien: An Algebraic Characterization of Data and Timed Languages. CONCUR 2001: 248-261

Thomas Schwentick, Denis Thérien, Heribert Vollmer: Partially-Ordered Two-Way Automata: A New Characterization of DA. Developments in Language Theory 2001: 239-250

David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, Denis Thérien: The Crane Beach Conjecture. LICS 2001: 187-196

Cristopher Moore, Pascal Tesson, Denis Thérien: Satisfiability of Systems of Equations over Finite Monoids. MFCS 2001: 537-547

Martin Beaudry, François Lemieux, Denis Thérien: Star-Free Open Languages and Aperiodic Loops. STACS 2001: 87-98

Ricard Gavaldà, Denis Thérien: Learning Expressions over Monoids. STACS 2001: 283-293

Howard Straubing, Denis Thérien: Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables. STACS 2001: 551-562

Pascal Tesson, Denis Thérien: The Computing Power of Programs over Finite Monoids. Electronic Colloquium on Computational Complexity (ECCC) 8(5) (2001)

Pierre Péladeau, Denis Thérien: On the Languages Recognized by Nilpotent Groups (a translation of "Sur les Langages Reconnus par des Groupes Nilpotents"). Electronic Colloquium on Computational Complexity (ECCC) 8(40) (2001)

Mikael Goldmann, Alexander Russell, Denis Thérien: An ergodic theorem for read-once non-uniform deterministic finite automata. Inf. Process. Lett. 73(1-2): 23-28 (2000)

Cristopher Moore, Denis Thérien, François Lemieux, Joshua Berman, Arthur Drisko: Circuits and Expressions with Nonassociative Gates. J. Comput. Syst. Sci. 60(2): 368-394 (2000)

Alexis Maciel, Pierre Péladeau, Denis Thérien: Programs over semigroups of dot-depth one. Theor. Comput. Sci. 245(1): 135-148 (2000)

Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer: The Many Faces of a Translation. ICALP 2000: 890-901

David A. Mix Barrington, Pierre McKenzie, Cristopher Moore, Pascal Tesson, Denis Thérien: Equation Satisfiability and Program Satisfiability for Finite Monoids. MFCS 2000: 172-181

Alexis Maciel, Denis Thérien: Efficient Threshold Circuits for Power Series. Inf. Comput. 152(1): 62-73 (1999)

Augustin Baziramwabo, Pierre McKenzie, Denis Thérien: Modular Temporal Logic. LICS 1999: 344-351

Alexis Maciel, Denis Thérien: Threshold Circuits of Small Majority-Depth. Inf. Comput. 146(1): 55-83 (1998)

Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer: Nondeterministic NC¹ Computation. J. Comput. Syst. Sci. 57(2): 200-212 (1998)

Jean-François Raymond, Pascal Tesson, Denis Thérien: An Algebraic Approach to Communication Complexity. ICALP 1998: 29-40

Denis Thérien, Thomas Wilke: Over Words, Two Variables Are as Powerful as One Quantifier Alternation. STOC 1998: 234-240

Martin Beaudry, Pierre McKenzie, Pierre Péladeau, Denis Thérien: Finite Moniods: From Word to Circuit Evaluation. SIAM J. Comput. 26(1): 138-152 (1997)

Pierre Péladeau, Howard Straubing, Denis Thérien: Finite Semigroup Varieties Defined by Programs. Theor. Comput. Sci. 180(1-2): 325-339 (1997)

Joshua Berman, Arthur Drisko, François Lemieux, Cristopher Moore, Denis Thérien: Circuits and Expressions with NOn-Associative Gates. IEEE Conference on Computational Complexity 1997: 193-203

Martin Beaudry, François Lemieux, Denis Thérien: Finite Loops Recognize Exactly the Regular Open Languages. ICALP 1997: 110-120

Birgit Jenner, Pierre McKenzie, Denis Thérien: Logspace and Logtime Leaf Languages. Inf. Comput. 129(1): 21-33 (1996)

Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer: Nondeterministic NC¹ Computation. IEEE Conference on Computational Complexity 1996: 12-21

Denis Thérien, Thomas Wilke: Temporal Logic and Semidirect Products: An Effective Characterization of the Until Hierarchy. FOCS 1996: 256-263

Howard Straubing, Denis Thérien, Wolfgang Thomas: Regular Languages Defined with Generalized Quanifiers. Inf. Comput. 118(2): 289-301 (1995)

Pierre McKenzie, Denis Thérien: Special Issue on Circuit Complexity: Foreword. Computational Complexity 4: 297-300 (1994)

Denis Thérien: Circuits Constructed with Mod_q Gates Cannot Compute "And" in Sublinear Size. Computational Complexity 4: 383-388 (1994)

Birgit Jenner, Pierre McKenzie, Denis Thérien: Logspace and Logtime Leaf Languages. Structure in Complexity Theory Conference 1994: 242-254

Clemens Lautemann, Thomas Schwentick, Denis Thérien: Logics For Context-Free Languages. CSL 1994: 205-216

Alexis Maciel, Denis Thérien: Threshold Circuits for Iterated Multiplication: Using AC0 for Free. STACS 1993: 545-565

Jean-Eric Pin, Howard Straubing, Denis Thérien: Some Results on the Generalized Star-Height Problem. Inf. Comput. 101(2): 219-250 (1992)

Martin Beaudry, Pierre McKenzie, Denis Thérien: The Membership Problem in Aperiodic Transformation Monoids. J. ACM 39(3): 599-616 (1992)

David A. Mix Barrington, Kevin J. Compton, Howard Straubing, Denis Thérien: Regular Languages in NC¹. J. Comput. Syst. Sci. 44(3): 478-499 (1992)

Denis Thérien: Circuits Constructed with MOD^q Gates Cannot Compute AND in Sublinear Size. LATIN 1992: 498-502

Pierre McKenzie, Pierre Péladeau, Denis Thérien: NC¹: The Automata-Theoretic Viewpoint. Computational Complexity 1: 330-359 (1991)

David A. Mix Barrington, Howard Straubing, Denis Thérien: Non-Uniform Automata Over Groups. Inf. Comput. 89(2): 109-132 (1990)

Denis Thérien: Programs over Aperiodic Monoids. Theor. Comput. Sci. 64(3): 271-280 (1989)

Pierre McKenzie, Denis Thérien: Automata Theory Meets Circuit Complexity. ICALP 1989: 589-602

Martin Beaudry, Pierre McKenzie, Denis Thérien: Testing Membership: Beyond Permutation Groups (Extended Abstract). STACS 1989: 388-399

Jean-Eric Pin, Howard Straubing, Denis Thérien: New Results on the Generalized Star-Height Problem. STACS 1989: 458-467

Denis Thérien: Categories Et Langages De Dot-Depth Un. ITA 22(4): 437-445 (1988)

David A. Mix Barrington, Denis Thérien: Finite monoids and the fine structure of NC¹. J. ACM 35(4): 941-952 (1988)

Howard Straubing, Denis Thérien, Wolfgang Thomas: regular Languages Defined with Generalized Quantifiers. ICALP 1988: 561-575

Howard Straubing, Denis Thérien: Finite automata and computational complexity. Formal Properties of Finite Automata and Applications 1988: 199-233

David A. Mix Barrington, Denis Thérien: Non-Uniform Automata Over Groups. ICALP 1987: 163-173

David A. Mix Barrington, Denis Thérien: Finite Monoids and the Fine Structure of NC¹. STOC 1987: 101-109

Alex Weiss, Denis Thérien: Varieties of Finite Categories. ITA 20(3): 357-366 (1986)

Denis Thérien: Classification of Finite Monoids: The Language Approach. Theor. Comput. Sci. 14: 195-208 (1981)

Denis Thérien: Languages of Nilpotent and Solvable Groups (Extended Abstract). ICALP 1979: 616-632