| Laura Chaubard, Jean-Eric Pin and Howard Straubing, First-order formulas with modular predicates, Proc. 21st IEEE Symposium on Logic in Computer Science (LICS), (2006), 211-220. |
| Laura Chaubard, Jean-Eric Pin and Howard Straubing, Actions, Wreath Products of C-varieties, and Concatenation Product, Theoretical Computer Science 356 (2006), 73-89. |
| Howard Straubing and Denis Therien, A Note on Mod p-Mod m Circuits, Theory of Computing Systems 39 (2006), 699-706. |
| Amitabha Roy and Howard Straubing, Definability of languages by generalized fisrst-order formulas over (N,+), in Proc. 23rd STACS, LNCS 3884 (2006), 35-50. Expanded version to appear in SIAM J. Computing. |
| Frederic Green, Amitabha Roy and Howard Straubing. Bounds on an exponential sum arising in boolean circuit complexity. C.R. Acad. Sci. Paris,Ser. I 341:279-282, 2005. |
| Eduardo Duenez, Steven Miller, Amitabha Roy and Howard Straubing. Incomplete Quadratic Exponential Sums in Several Variables. J. Number Theory, in press. |
| Howard Straubing, Inexpressibility Results for Regular Languages in Nonregular Settings, in C. de Felice and A. Restivo (eds.), Developments in Language Theory, LNCS 3572, (2005),69-77. |
| Jean-Eric Pin and Howard Straubing. Some results on C-varieties. RAIRO: Theoretical Informatics. 39:239-262, 2005. |
|
Howard Straubing and 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. [ps] [pdf] |
|
Howard Straubing. Finite semigroups and the logical description of
regular languages. In Semigroups, algorithms, automata and
languages (Coimbra, 2001), pages 463-474. World Sci. Publishing,
River Edge, NJ, 2002. |
|
Howard Straubing. On logical descriptions of regular languages. In LATIN
2002: Theoretical informatics (Cancun), volume 2286 of Lecture
Notes in Comput. Sci., pages 528-538. Springer, Berlin, 2002. [ps] [pdf] |
|
Howard Straubing and Denis Thérien. Weakly iterated block
products of finite monoids. In LATIN 2002: Theoretical informatics
(Cancun), volume 2286 of Lecture Notes in Comput. Sci.,
pages 91-104. Springer, Berlin, 2002. [ps] [pdf] |
|
Howard Straubing and Denis Thérien. Regular languages defined by
generalized first-order formulas with a bounded number of bound
variables. In STACS 2001 (Dresden), volume 2010 of Lecture
Notes in Comput. Sci., pages 551-562. Springer, Berlin, 2001. (Conference version of [1].) |
|
Kevin J. Compton and Howard Straubing. Characterizations of
regular languages in low level complexity classes. In Current
trends in theoretical computer science, pages 235-246. World Sci.
Publishing, River Edge, NJ, 2001. |
|
Howard Straubing. Languages defined with modular counting quantifiers. Inform.
and Comput., 166(2):112-132, 2001. [ps] [pdf] |
|
Howard Straubing. When can one finite monoid simulate another? In Algorithmic
problems in groups and semigroups (Lincoln, NE, 1998), Trends
Math., pages 267-288. Birkhäuser Boston, Boston, MA, 2000. [ps] [pdf] |
|
David A. Mix Barrington and Howard Straubing. Lower bounds for
modular counting by circuits with modular gates. Comput. Complexity,
8(3):258-272, 1999. |
|
Howard Straubing. Languages defined with modular counting quantifiers
(extended abstract). In STACS 98 (Paris, 1998), volume 1373 of Lecture
Notes in Comput. Sci., pages 332-343. Springer, Berlin, 1998. (Conference version of [7].) |
|
Pierre Péladeau, Howard Straubing, and Denis Thérien.
Finite semigroup varieties defined by programs. Theoret. Comput.
Sci., 180(1-2):325-339, 1997. |
|
Howard Straubing. Finite models, automata, and circuit complexity. In Descriptive
complexity and finite models (Princeton, NJ, 1996), volume 31
of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages
63-96. Amer. Math. Soc., Providence, RI, 1997. |
| H. Straubing, D. Thérien, and W. Thomas. Logics for regular languages, finite monoids, and circuit complexity. In Semigroups, formal languages and groups (York, 1993), volume 466 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pages 119-146. Kluwer Acad. Publ., Dordrecht, 1995. [ps] [pdf] |
|
David A. Mix Barrington and Howard Straubing. Superlinear lower
bounds for bounded-width branching programs. J. Comput. System Sci.,
50(3, part 1):374-381, 1995. Sixth Annual Conference on Structure in
Complexity Theory (Chicago, IL, 1991). [ps] [pdf] |
|
Howard Straubing, Denis Thérien, and Wolfgang Thomas. Regular
languages defined with generalized quantifiers. Inform. and Comput.,
118(2):289-301, 1995. [ps] [pdf] |
|
David A. Mix Barrington and Howard Straubing. Complex polynomials
and circuit lower bounds for modular counting. Comput. Complexity,
4(4):325-338, 1994. Special issue on circuit complexity (Barbados,
1992). [ps] [pdf] |
| Richard Beigel and Howard Straubing. The Power of local self-reductions', in Proc. Tenth Annual Conference on Structure in Complexity (Minneapolis 1995). [ps] [pdf] |
|
David A. Mix Barrington and Howard Straubing. Complex polynomials
and circuit lower bounds for modular counting. In LATIN '92 (Sao
Paulo, 1992), volume 583 of Lecture Notes in Comput. Sci.,
pages 24-31. Springer, Berlin, 1992. (Conference version of [16].) |
|
Howard Straubing. Circuit complexity and the expressive power of
generalized first-order formulas. In Automata, languages and
programming (Vienna, 1992), volume 623 of Lecture Notes in
Comput. Sci., pages 16-27. Springer, Berlin, 1992. |
|
J.-E. Pin, H. Straubing, and D. Thérien. Some results
on the generalized star-height problem. Inform. and Comput.,
101(2):219-250, 1992. |
|
H. Straubing and P. Weil. On a conjecture concerning
dot-depth two languages. Theoret. Comput. Sci., 104(2):161-183,
1992. |
|
David A. Mix Barrington, Kevin Compton, Howard Straubing, and
Denis Thérien. Regular languages in NC 1. J.
Comput. System Sci., 44(3):478-499, 1992. |
|
Howard Straubing. Automata, logic and computational complexity. In Monoids
and semigroups with applications (Berkeley, CA, 1989), pages
467-492. World Sci. Publishing, River Edge, NJ, 1991. |
|
Howard Straubing. Constant-depth periodic circuits. Internat. J.
Algebra Comput., 1(1):49-87, 1991. |
|
David A. Mix Barrington, Howard Straubing, and Denis
Thérien. Nonuniform automata over groups. Inform. and Comput.,
89(2):109-132, 1990. |
|
David A. Mix Barrington, Neil Immerman, and Howard Straubing. On
uniformity within NC 1. J. Comput. System Sci.,
41(3):274-306, 1990. |
|
Howard Straubing and Denis Thérien. Finite automata and
computational complexity. In Formal properties of finite automata
and applications (Ramatuelle, 1988), volume 386 of Lecture
Notes in Comput. Sci., pages 199-233. Springer, Berlin, 1989. |
|
Howard Straubing. The wreath product and its applications. In Formal
properties of finite automata and applications (Ramatuelle, 1988),
volume 386 of Lecture Notes in Comput. Sci., pages 15-24.
Springer, Berlin, 1989. |
|
J.-E. Pin, H. Straubing, and D. Thérien. New results
on the generalized star-height problem. In STACS 89 (Paderborn,
1989), volume 349 of Lecture Notes in Comput. Sci., pages
458-467. Springer, Berlin, 1989. (Conference version of [20].) |
|
Howard Straubing, Denis Thérien, and Wolfgang Thomas. Regular
languages defined with generalized quantifiers. In Automata,
languages and programming (Tampere, 1988), volume 317 of Lecture
Notes in Comput. Sci., pages 561-575. Springer, Berlin, 1988. (Conference version of [15].) |
|
Howard Straubing and Denis Thérien. Partially ordered finite
monoids and a theorem of I. Simon. J. Algebra, 119(2):393-399,
1988. |
|
Howard Straubing. Semigroups and languages of dot-depth two. Theoret.
Comput. Sci., 58(1-3):361-378, 1988. Thirteenth International
Colloquium on Automata, Languages and Programming (Rennes, 1986). |
|
Jean-Eric Pin, Howard Straubing, and Denis Thérien. Locally
trivial categories and unambiguous concatenation. J. Pure Appl.
Algebra, 52(3):297-311, 1988. |
|
Howard Straubing and Denis Thérien. Finite J-trivial monoids and
partially ordered monoids. In Semigroups and their applications
(Chico, Calif., 1986), pages 183-189. Reidel, Dordrecht, 1987. |
|
Howard Straubing. Applications of the theory of automata in
enumeration. Discrete Math., 64(2-3):269-279, 1987. |
|
Howard Straubing. Semigroups and languages of dot-depth 2. In Automata,
languages and programming (Rennes, 1986), volume 226 of Lecture
Notes in Comput. Sci., pages 416-423. Springer, Berlin, 1986. (Conference version of [32].) |
|
J.-E. Pin and H. Straubing. Monoids of upper triangular matrices.
In Semigroups (Szeged, 1981), volume 39 of Colloq.
Math. Soc. János Bolyai, pages 259-272. North-Holland,
Amsterdam, 1985. |
|
Howard Straubing. Finite semigroup varieties of the form V D.
J. Pure Appl. Algebra, 36(1):53-94, 1985. |
|
Jean-Eric Pin, Howard Straubing, and Denis Thérien. Small
varieties of finite semigroups and extensions. J. Austral. Math.
Soc. Ser. A, 37(2):269-281, 1984. |
|
Christophe Reutenauer and Howard Straubing. Inversion of matrices over
a commutative semiring. J. Algebra, 88(2):350-360, 1984. [ |
|
Howard Straubing. The Burnside problem for semigroups of matrices. In Combinatorics
on words (Waterloo, Ont., 1982), pages 279-295. Academic Press,
Toronto, ON, 1983. |
|
Howard Straubing. A combinatorial proof of the Cayley-Hamilton theorem.
Discrete Math., 43(2-3):273-279, 1983. |
|
Howard Straubing. The variety generated by finite nilpotent monoids. Semigroup
Forum, 24(1):25-38, 1982. |
|
Howard Straubing. Relational morphisms and operations on recognizable
sets. RAIRO Inform. Théor., 15(2):149-159, 1981. |
|
Jean-Eric Pin and Howard Straubing. Remarques sur le
dénombrement des variétés de monoï des finis.
C. R. Acad. Sci. Paris Sér. I Math.,
292(1):111-113, 1981. |
|
Howard Straubing. A generalization of the Schützenberger product
of finite monoids. Theoret. Comput. Sci., 13(2):137-150, 1981. |
|
Howard Straubing. On finite J-trivial monoids. Semigroup Forum,
19(2):107-110, 1980. |
|
Howard Straubing. Recognizable sets and power sets of finite
semigroups. Semigroup Forum, 18(4):331-340, 1979. |
|
Howard Straubing. Aperiodic homomorphisms and the concatenation product
of recognizable sets. J. Pure Appl. Algebra, 15(3):319-327,
1979. |
|
Howard Straubing. Families of recognizable sets corresponding to
certain varieties of finite monoids. J. Pure Appl. Algebra,
15(3):305-318, 1979. [ |