Research and Expository Articles

`Families of recognizable sets corresponding to certain varieties of finite monoids', Journal of Pure and Applied Algebra
15 (1979), 305-318.

`Aperiodic morphisms and the concatenation product of recognizable sets', Journal of Pure and Applied Algebra 15 (1979), 319-327.

`On finite J-trivial monoids',  Semigroup Forum 19 (1980), 107-110.

`Recognizable sets and power sets of finite semigroups', Semigroup Forum 19 (1980), 331-340.

`A generalization of the Schutzenberger product of finite monoids', Theoretical Computer Science 13 (1981), 137-150

(with J. E. Pin) `Remarques sur le denombrement des varietes de monoides finis', C. R. Acad. Sci. Paris  t. 292 (January, 1981).

`Relational morphisms and operations on recognizable sets',  RAIRO (Informatique theorique) 15 (1981), 149-159.

`The variety generated by finite nilpotent monoids', Semigroup Forum 24 (1982), 25-38.

`A combinatorial proof of the Cayley-Hamilton theorem',  Discrete Mathematics  43  (1983), 273-279.

(with C. Reutenauer) `Inversion of matrices over a commutative semiring', Journal of Algebra 88 (1984), 350-360.

`The Burnside problem for semigroups of matrices', in L. Cummings, ed., Combinatorics on Words (Academic Press, New York, 1983), 279-296.

(with J. E. Pin and D. Therien) `Small varieties of finite semigroups', Journal of the Australian Mathematical Society A   37 (1984), 269-281.

(with J.E. Pin) `Monoids of upper triangular matrices', Colloquia Math. Soc. J. Bolyai  39 (dated 1981; appeared 1985), 259-272.

`Finite semigroup varieties of the form  V*D, Journal of Pure and Applied Algebra 36 (1985),  53-94.

`Semigroups and languages of dot-depth two' (extended abstract),  in Proc. 13th ICALP, Lecture Notes in Computer Science  218, Springer,  Berlin, 1986, 416-423.

`Applications of the theory of automata in enumeration', Discrete Mathematics 64 (1987), 269-279.

(with J. E. Pin and D. Therien) `Locally trivial categories and unambiguous
concatenation', Journal of Pure and Applied Algebra 52 (1988) 297-311.

(with D. Therien and W. Thomas) `Regular languages defined with generalized quantifiers', in  Proc. 15th ICALP, Lecture Notes in Computer Science317,  Springer, Berlin (1988) 561-575

`Semigroups and Languages of dot-depth two',  Theoretical Computer Science   58  (1988), 361-378.

(with D. Therien) `Partially ordered finite monoids and a theorem of I. Simon', Journal of Algebra 119 (1988), 393-399.

(with D.A. Mix Barrington and N. Immerman)  `On uniformity in NC1', J. Comp. Syst. Sci.  41 (1990), 274-306.

(with D. A. Mix Barrington and D. Th\'erien), `Non-Uniform automata over groups', Information and Computation  89 (1990) 109-132

(with D. Therien), `Finite automata and computational complexity' in Formal Properties of Finite Automata and  Applications, (J.E. Pin, ed.) Lecture Notes in Computer Science 386, Springer, Berlin (1990) 199-223.

`The wreath product and its applications' in Formal Properties of Finite Automata and  Applications, (J.E. Pin, ed.)  Lecture Notes in Computer Science 386, Springer, Berlin (1990) 15-24.

`Constant-depth periodic circuits', International J. Algebra and Computation 1 , (1991), 49-87.

`Automata, logic and computational complexity', in Monoids and Semigroups with Applications, (J. Rhodes, ed.), World Scientific, (1991) 467-492

(with D. A. Mix Barrington) `Superlinear lower bounds for bounded-width branching programs', in
 Proc. 6th IEEE Structure in Complexity Theory Conference (1991) 305-314.  Journal version in J. Comp. Sys. Sci  [ps]    [pdf]

 (with D. A. Mix Barrington, K. Compton, and D. Therien), `Regular Languages in NC1, J. Comp. Syst. Sci. 44 (1992) 478-499

(with P. Weil) `On a conjecture concerning dot-depth two languages', Theoretical Computer Science  104  (1992) 161-183.

(with J.E. Pin and D. Th erien) `New Results on the Generalized Star-Height Problem', Information and Computation 101  (1992).

(with D. A. Mix Barrington) `Complex polynomials and circuit lower bounds for modular counting', in
Proceedings of LATIN '92 conference, Lecture Notes in Computer Science583,  Springer, Berlin (1992) 24-31; journal version in Computational Complexity 4 (1994) 325-338. [ps]   [pdf]

 (with K. J. Compton) `Characterizations of the regular languages in low-level complexity classes',  Bulletin of the European
Association for Theoretical Computer Science  48  (1992) 134-142.

`Circuit complexity and the expressive power of generalized first-order formulas', in Proc.  ICALP 92,  Lecture Notes in Computer Science   623 Springer, Berlin (1992) 16-27. [ps]  [pdf]

(with D. A. Mix Barrington) `Lower Bounds for Modular Counting by Circuits with Modular Gates', in Proceedings of the 2nd Latin American Symposium  on Theoretical Computer Science, Lecture Notes in Computer Science
911 Springer, Berlin (1995), 60-71. [ps]  [pdf]

(with D. Therien and W. Thomas) `Regular languages defined with generalized
quantifiers',   Information and Computation 118 (1995) 289-301. [ps]   [pdf]

(with R. Beigel) `The Power of Local Self-Reductions', in Proceedings of the Tenth IEEE Conference on Structure in Complexity Theory, 1995. [ps]    [pdf]

(with D. Therien and W. Thomas) `Logics for Regular Languages, Finite Monoids, and Circuit Complexity', in J. Fountain(ed.),  Semigroups, Formal Languages and Groups,  Kluwer Academic Publishers (1995), 119-146. [ps]  [pdf]

`Finite Models, Automata, and Circuit Complexity' in N. Immerman and P. Kolaitis (eds.)  Descriptive Complexity and Finite Models,  DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical
Society (1997) 63-96.

(with P. P eladeau and D. Th erien) `Finite Semigroup Varieties Defined by Programs',  Theoretical Computer Science, 180 (1997) 325-339

`Languages Defined with Modular Counting Quantifiers', in Proc. 15th STACS , Lecture Notes in Computer Science  1373 , Springer, Berlin (1998) 332-343.

(with D. Barrington) `Lower Bounds for Modular Counting by Circuits with Modular Gates',  Computational Complexity  8  (1999) 258-272.

`When Can One Finite Monoid Simulate Another?', in J.C. Birget, S. Margolis, J. Meakin and M. Sapir (eds.)  Algorithmic Problems in Groups and Semigroups,  Birkhauser, Boston (2000) 267-288. [ps] [pdf]

`Languages Defined by Modular Quantifiers', Information and Computation 166 (2001) 112-132.. [ps]   [pdf]

(with D. Therien) `Regular Languages Defined by Generalized First-order Formulas with a Bounded Number of Bound Variables',  in Proc. 18th STACS, Lecture Notes in Computer Science 2010,
Springer, Berlin (2001). Journal version to appear in Theory of Computing Systems.  [ps]   [pdf]

(with D. Therien) 'Weakly Iterated Block Products of Finite Monoids',  in Proceedings of LATIN 2002, Springer Lecture Notes in Computer Science 2286. [ps]  [pdf]

'On the Logical Description of Regular Languages',  in Proceedings of LATIN 2002, Springer Lecture Notes in Computer Science 2286. [ps]   [pdf]
 
 
 

Book

Finite Automata, Formal Logic, and Circuit Complexity, Birkhauser, Boston, 1994.