Publications

Journal Articles
  1. Tesson, P. and Thérien, D., Logic Meets Algebra: the Case of Regular Languages, accepted in Logical Methods in Computer Science, 2006.
  2. Ambainis, A., Beaudry, M, Golovkins, M., Kikusts, A., Mercer, M. and Thérien, D., Algebraic Results on Quantum Automata, Theory of Computing Systems, Vol. 39, No. 1, 165-188, 2006.
  3. Klima, O., Tesson, P., and Thérien, D., Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups, electronic version in Theory of Computing Systems, 2005.
  4. Barrington, D. A. M., Immerman, N., Lautemann, C., Schweikardt, N. and Thérien, D., First-Order Expressibility of Languages with Neutral Letters Or: The Crane Beach Conjecture, Journal of Computer and System Sciences, vol. 70, 101-127, 2005.
  5. Borchert, B., Lange, K-J., Stephan, F., Tesson, P and Thérien, D. The Dot-Depth and the Polynomial Hierarchy Correspond on the Delta Levels, International Journal of Foundations of Computer Science, Vol. 16, No. 4, 625-644, 2005
  6. Tesson, P, and Thérien, D., Complete Classification for the Communication Complexity of Regular Languages, Theory of Computing Systems, Vol. 38, No. 2, 135-159, 2005.
  7. Thérien, D., Imre Simon: An Exceptional Graduate Student, RAIRO-Theoretical Informatics and Applications, Vol. 39, No. 1, 297-304, 2005.
  8. Gavalda, R., Tesson, P. and Thérien, D., Learning Expressions and Programs over Finite Monoids, accepted in Information and Computation, 2004.
  9. Tesson, P, and Thérien, D., Monoids and Computations, International Journal of Algebra and Computation, vol. 14, nos. 5 & 6, 2004.
  10. Straubing, H. and Thérien, D., A Note on MODp - MODm Circuits, accepted in Theory of Computing Systems, 2003.
  11. Thérien, D. and Wilke, T., Nesting Until and Since in Linear Temporal Logic, Theory of Computing Systems, 37(1), 111-131, 2003.
  12. Bouyer, P., Petit, A. and Thérien, D., An Algebraic Approach to Data Languages and Timed Languages, Information and Computation, vol. 182(2), 137-162, 2003.
  13. Straubing, H. and Thérien, D., Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables, Theory of Computing Systems, vol. 36(1), 29-69, 2003.
  14. McKenzie, P., Schwentick, T., Thérien, D. and Vollmer, H., The Many Faces of Translations, accepted in Journal of Computer and System Sciences, 2002.
  15. Tesson, P. and Thérien, D., The Computing Power of Programs over Finite Monoids, Journal of Automata, Languages and Combinatorics, vol. 7(2), 777-798, 2002.
  16. Thérien, D. and Wilke, T., Temporal Logic and Semidirect Products: an Effective Characterization of the Until Hierachy, SIAM Journal on Computing, vol. 31(3), 777-798, 2002.
  17. Lemieux, F., Moore, C. and Thérien D., Subtree-counting Groupoids, Quasigroups and Related Systems, vol. 8, 2001, 45-65.
  18. Raymond, J.F., Tesson, P. and Thérien, D., Multiparty Communication Complexity in Finite Monoids, in Algorithmic Problems in Groups and Semigroups, Birkhauser, 2000, 217-234.
  19. Maciel, A., Péladeau, P. and Thérien, D., Programs over semigroups of dot-depth one, Theoretical Computer Science, 245, 2000, 135-148.
  20. Goldmann, M., Russell, A. and Thérien, D., An Ergodic Theorem for Read-Once Non-Uniform Deterministic Finite Automata, Information Processing Letters 73, 2000, 23-28.
  21. Berman, J., Drisko, A., Lemieux, F., Moore, C. and Thérien, D., Circuits and Expressions with Non-Associative Gates, Journal of Computer and System Sciences 60, 2000, 368-394.
  22. Maciel, A. and Thérien, D., Efficient Threshold Circuits for Power Series, Information and Computation, vol. 152, 1999, 62-73.
  23. Maciel, A. and Thérien, D., Threshold Circuits of Small Majority-Depth, Information and Computation 146, 1998, 55-83.
  24. Caussinus, H., McKenzie, P., Thérien, D. and Vollmer, H., Nondeterministic NC1 Computation, Journal of Computer and System Sciences, vol. 57,1998, 200-212.
  25. Beaudry, M., McKenzie, P., Péladeau, P. and Thérien, D., Finite Monoids: From Word to Circuit Evaluation, SIAM Journal on Computing, vol. 26, no. 1, 1997, 138-152.
  26. Péladeau, P., Straubing, H. and Thérien, D., Finite Semigroup Varieties Defined by Programs, Theoretical Computer Science, vol. 180, no 1-2, 1997, 325-340.
  27. Jenner, B., McKenzie, P. and Thérien, D., Logspace and Logtime Leaf Languages, Information and Computation, vol, 120, no 1, 1996, 21-33.
  28. Straubing, H., Thérien, D. and Thomas, W., Regular Languages Defined with Generalized Quantifiers, Information and Computation, vol. 118, no 2, 1995, 289-301.
  29. Thérien, D., Circuits Constructed with MODq Gates Cannot Compute AND in Sublinear Size, computational complexity, vol. 4, no. 4, 1994, 383-388.
  30. Pin, J.-E. and Thérien, D., The Bideterministic Concatenation Product, International Journal of Algebra and Computation, vol. 3, no. 4, 1993, 535-555.
  31. Pin, J.E., Straubing, H. and Thérien, D., Some Results on the Generalized Star-height Problem, Information and Computation, vol. 101, no. 2, 1992, 219-250.
  32. Beaudry, M., McKenzie, P. and Thérien, D., The Membership Problem in Aperiodic Transformation Monoids, Journal of ACM, no. 39, vol. 2, 1992, 599-616.
  33. Barrington, D.A., Compton, K., Straubing, H. and Thérien, D., Regular Languages in NC1, Journal of Computer and System Sciences, vol. 44, no. 3, 1992, 478-499.
  34. McKenzie, P., Péladeau, P. and Thérien, D., NC1: the Automata-theoretic Viewpoint, computational complexity, vol. 1, 1991, 330-359.
  35. Thérien, D., Two-sided Wreath Product of Categories, Journal of Pure and Applied Algebra, vol. 74, 1991, 307-315.
  36. Barrington, D.A., Straubing, H. and Thérien, D., Non-uniform Automata over Groups, Information and Computation, vol. 89, no. 2, 1990, 109-132.
  37. Thérien, D., Parallel Computations over Aperiodic Monoids, Theoretical Computer Science 64, 1989, 271-280.
  38. Barrington, D. and Thérien, D., Finite Monoids and the Fine Structure of NC1, Journal of ACM, vol. 35, no.4, 1988, 941-952.
  39. Thérien, D., On the Equation xt = xt+q in Categories, Semigroup Forum, vol. 37, 1988, 265-271.
  40. Straubing, H. and Thérien, D., Partially Ordered Finite Monoids and a Theorem of I. Simon, Journal of Algebra, vol. 119, no. 2, 1988, 393-399.
  41. Pin, J.E., Straubing, H. and Thérien, D., Locally Trivial Categories and Unambiguous Concatenation, Journal of Pure and Applied Algebra, vol. 52, no. 3, 1988, 297-311.
  42. Thérien, D., Catégories et Langages Rationnels de Dot-depth Un, Informatique théorique et Applications/Theoretical Informatics and Applications, vol. 22, no. 4, 1988, 437-445.
  43. Thérien, D. and Péladeau, P., Sur les Langages Reconnus par des Groupes Nilpotents, Comptes-rendus de l'Académie des Sciences de Paris, t. 306, Série I, 1988, 93-95.
  44. Weiss, A. and Thérien D., Varieties of Finite Categories, Revue d'Automatique, d'Informatique et de Recherche Opérationnelle, vol. 20, 1986, 357-366.
  45. Thérien, D. and Weiss, A., Graph Congruences and Wreath Products, Journal of Pure and Applied Algebra, vol. 36, 1985, 205-215.
  46. Pin, J.-E., Straubing, H. and Thérien, D., Small Varieties of Finite Semigroups and Extensions, Journal of the Australian Mathematical Society, Series A, vol. 37, 1984, 269-281.
  47. Thérien, D., A Language Theoretic Interpretation of Schutzenberger Representations, Semigroup Forum, vol. 28, 1984, 235-248.
  48. Thérien, D., Sur les Monoides Dont Tous les Groupes Sont Résolubles, Semigroup Forum, vol. 26, 1983, 89-101.
  49. Thérien, D., Classification of Finite Monoids: the Language Approach, Theoretical Computer Science, vol. 14, 1981, 195-208.

-----




Conferences
  1. Chattopadhyay, A., Goyal, N, Pudlak, P. and Thérien, D., Lower Bounds for Circuits with MOD m Gates, accepted at the 48th IEEE FOCS Conference, 2006.
  2. Tesson, P. and Thérien, D., An Algebraic Point of View on the Crane Beach Conjecture , accepted in CSL, 2006.
  3. Dalmau, V., Gavalda, R., Tesson, P. and Thérien, D., Tractable Clones of Polynomials over Semigroups , Proceedings of the 11th International Conference on Principles and Practices of Constraint Programming, LNCS 2709, 196-210, 2005.
  4. Tesson P. and Thérien, D., Restricted Two-Variables FO+MOD Sentences, Circuits and Communication Complexity, Proceedings of the 32nd ICALP, LNCS 2580, Springer 2005, 526-538.
  5. Beaudry, M., Lemieux, F. and Thérien, D., Groupoids that recognize only regular languages, Proceedings of the 32nd ICALP, LNCS 3580, Springer, 2005, 421-433.
  6. Koucký, M., Pudlák, P., and Thérien, D., Bounded-depth circuits: Separating gates from wires . Proceedings of the 37th ACM STOC Converence, 2005, 257-265.
  7. Borchert, B., Lange, K-J., Stephan, F., Tesson, P and Thérien, D., The Dot-Depth and the Polynomial Hierarchy Correspond on the Delta Levels, Proceedings of the 8th Conference on Devolopments in Language Theory, LNCS 3340, 2004, 89-101.
  8. Ambainis, A., Beaudry, M, Golovkins, M., Kikusts, A., Mercer, M. and Thérien, D., Algebraic Results on Quantum Automata, Proceedings of the 21st STACS conference, LNCS 2996, Springer, 2004, 93-104.
  9. Chattopadhyay, A. and Thérien, D., Locally Commutative Categories, Proceedings of 30th ICALP, LNCS 2719, Springer, 2003, 984-995.
  10. Tesson, P. and Thérien, D., Complete Classification for the Communication Complexity of Regular Languages, Proceedings of the 20th STACS conference, LNCS 2607, Springer, 2003, 62-73.
  11. Gavalda, R. and Thérien, D., Algebraic Characterization of Small Classes of Boolean Functions, Proceedings of the 20th STACS conference, LNCS 2607, Springer, 2003, 331-342.
  12. Tesson, P. and Thérien D., Diamonds are Forever: the Variety DA, in Semigroups, Algorithms, Automata and Languages, G.M.S. Gomes, P.V. Silva and J.-E. Pin eds., WSP, 2002, 475-500.
  13. Thérien, D. and Wilke, T., Nesting Until and Since in Linear Temporal Logic, Proceedings of the 19th STACS conference, LNCS 2285, Springer, 2002, 455-476.
  14. Straubing, H. and Thérien D., Weakly Iterated Block Product of Finite Monoids, Proceedings of the 4th LATIN conference, LNCS 2286, Springer, 2002, 91-104.
  15. Beaudry, M., Lemieux, F. and Thérien D., Star-free Open Languages and Aperiodic Loops, Proceedings of the 18th STACS conference, LNCS 1010, Springer, 2001, 87-98.
  16. Gavalda, R. and Thérien, D., Learning Expressions over Finite Monoids, Proceedings of the 18th STACS conference, LNCS 1010, Springer, 2001, 283-293.
  17. Straubing, H. and Thérien, D., Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables, Proceedings of the 18th STACS conference, LNCS 1010, Springer, 2001, 551-562.
  18. Barrington, D. A. M., Immerman, N., Lautemann, C., Schweikardt, N. and Thérien, D., The Crane Beach Conjecture, Proceedings of IEEE LICS Symposium, 2001, 187-196.
  19. Moore, C., Tesson, P. and Thérien, D., Satisfiability of Systems of Equations over Finite Monoids, Proceedings of MFCS 2001, LNCS 2136, Springer, 537-547.
  20. Schwentick, T., Thérien, D. and Vollmer H., Partially Ordered Two-way Automata: a New Characterization of DA, Proceedings of DLT 2001, 242-253.
  21. Bouyer, P., Petit, A. and Thérien, D., An Algebraic Characterization of Data and Timed Languages, Proceedings of CONCUR 2001, LNCS 2154, Springer, 248-261.
  22. McKenzie, P., Schwentick, T., Thérien, D. and Vollmer, H., The Many Faces of a Translation, Proceedings of 27th ICALP, LNCS 1853, Springer, 2000, 890-901.
  23. Lemieux, F., Moore, C. and Thérien, D., Polyabelian Loops and Boolean Completeness, Commentationes Mathematicae Universitatis Carolinae, 41, 4, 2000, 671-686.
  24. Baziramwabo, A., McKenzie, P. and Thérien, D., Modular Temporal Logic, Proceedings of the 14th IEEE LICS Symposium, 1999, 344-351.
  25. Raymond, J.F., Tesson, P. and Thérien, D., An Algebraic Approach to Communication Complexity, Proceedings of the 25th ICALP, Lecture Notes in Computer Science 1443, Springer-Verlag, 1998, 29-40.
  26. Thérien, D. and Wilke, T., Over Words, Two Variables Are as Powerful as One Quantifier Alternation, Proceedings of the 30th ACM STOC Conference, 1998, 234-240.
  27. Bolduc, J.S., Broderick, G. and Thérien, D., From Stability to Tracking: Robustness of Cellular Automata Base Controllers, Proceedings of IEEE 1st International Conference on Intelligent Processing Systems, vol. 1, 1997, 619-624.
  28. Beaudry, M., Lemieux, F. and Thérien, D., Finite loops recognize exactly the regular open languages, Proceedings of the 24th ICALP, Lecture Notes in Computer Science 1256, Springer-Verlag, 1997,
  29. Berman, J., Drisko, A., Lemieux, F., Moore, C. and Thérien, D., Circuits and Expressions with Non-Associative Gates, Proceedings of the 12th IEEE Computational Complexity Conference, 1997, 193-203.
  30. Maciel, A., Péladeau, P. and Thérien, D., Programs over Semigroups of Dot-depth One, First International Conference on Semigroups and Algebraic Engineering, 1997.
  31. Thérien, D. and Wilke, T., Temporal Logic and Semidirect Products: an Effective Characterization of the Until Hierachy Proceedings of the 37th IEEE FOCS Conference, 1996, 256-263.
  32. Caussinus, H., McKenzie, P., Thérien, D. and Vollmer, H., Nondeterministic NC1 Computation, Proceedings of the 11th IEEE Computational Complexity Conference, 1996, 12-23.
  33. Lautemann, C., Schwentick, T. and Thérien, D., Logics for Context-free Languages, Proceedings of the 1994 Annual Conference of the European Association for Computer Science Logic, LNCS 933, 1995, 205-216.
  34. Straubing, H., Thérien, D. and Thomas, W., Logics for Regular Languages, Finite Monoids and Circuit Complexity Proceedings of the NATO Advanced Study Institute on Semigroups, Formal Languages and Groups, 1995, 119-146.
  35. Jenner, B., McKenzie, P. and Thérien, D., Logspace and Logtime Leaf Languages, Proceedings of the 9th IEEE Structure in Complexity Theory Conference, 1994, 242-254.
  36. Maciel, A. and Thérien, D., Threshold Circuits for Iterated Multiplication: Using AC0 for Free, Proceedings of the 10th STACS conference, Lecture Notes in Computer Science 665, Springer-Verlag, 1993, 545-554.
  37. Thérien, D., Circuits Constructed with MODq Gates Cannot Compute AND in Sublinear Size, Proceedings of the Latin American Theoretical Informatics Conference, Lecture Notes in Computer Science 583, Springer-Verlag, 1992, 498-502.
  38. Thérien, D., Une Approche Algébrique à la Théorie de la Complexité, in Parallélisme: modèles et complexité, Actes du Colloque ACFAS 89, 1990, 79-88.
  39. McKenzie, P. and Thérien, D., Automata Theory Meets Circuit Complexity, Proceedings of the 16th ICALP, Lecture Notes in Computer Science 372, Springer-Verlag, 1989, 589-602.
  40. Straubing, H. and Thérien, D., Finite Automata and Computational Complexity, in Formal Properties of Finite Automata and Applications, Lecture Notes in Computer Science 386, Springer-Verlag, 1989, 199-233.
  41. Beaudry, M., McKenzie, P. and Thérien, D., Testing Membership: Beyond Permutation Groups, Proceedings of the 6th STACS conference, Lecture Notes in Computer Science 349, Springer-Verlag, 1989, 388-399.
  42. Pin, J.E., Straubing, H. and Thérien, D., Some Results on the Generalized Star-height Problem, Proceedings of the 6th STACS conference, Lecture Notes in Computer Science 349, Springer-Verlag, 1989, 458-467.
  43. Straubing, H., Thérien, D. and Thomas, W., Regular Languages Defined with Generalized Quantifiers, Proceedings of the 15th ICALP, Lecture Notes in Computer Science 317, Springer-Verlag, 1988, 561-575.
  44. Barrington, D. and Thérien, D., Non-uniform Automata over Groups, Proceedings of the 14th ICALP, Lecture Notes in ComputerScience, Springer-Verlag, 1987, 163-173.
  45. Barrington, D. and Thérien, D., Finite Monoids and the Fine Structure of NC1 Proceedings of the 19th ACM STOC, 1987, 101-109.
  46. Thérien, D. and Sznajder-Glodowski, M., Finite Categories and Regular Languages, Proceedings of the Semester on Mathematical Problems in Computation Theory of the Stefan Banach International Mathematical Center, Warsaw, 1985, 395-402.
  47. Thérien, D., Subword Counting and Nilpotent Groups, in Combinatorics on Words, Progress and Perspectives, Larry Cummings ed., Academic Press, 1983, 297-306.
  48. Thérien, D., Languages of Nilpotent and Solvable Groups , Proceedings of the 6th ICALP, Lecture Notes in Computer Science 71, 1979, 616-632.

-----