|
||||||
| 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. [pdf] |
||||||
| Laura Chaubard, Jean-Eric Pin and Howard Straubing, Actions,
Wreath Products of C-varieties, and Concatenation Product, Theoretical Computer Science 356 (2006), 73-89. [pdf] |
||||||
| Howard Straubing and Denis Therien, A Note on Mod p-Mod m
Circuits, Theory of Computing
Systems 39 (2006),
699-706. [pdf] |
||||||
| 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: 9 (2005) 279-282. [pdf] | ||||||
| Eduardo Duenez, Steven Miller, Amitabha Roy and Howard Straubing. Incomplete Quadratic Exponential Sums in Several Variables. J. Number Theory, 116 (2006) 168-199. [pdf] | ||||||
| Howard Straubing, Inexpressibility Results for Regular
Languages in Nonregular Settings, in C. de Felice and A. Restivo
(eds.), Developments in Language
Theory, LNCS 3572, 69-77 (2005). [pdf] |
||||||
| Jean-Eric Pin and Howard Straubing. Some results on C-varieties. RAIRO: Theoretical Informatics. 39:239-262, 2005. [pdf] | ||||||
| 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] (Preliminary version in STACS 2001 (Dresden), volume 2010 of Lecture Notes in Comput. Sci., pages 551-562. Springer, Berlin, 2001.) |
||||||
| 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. [pdf] |
||||||
| 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] |
||||||
| 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] (Preliminary version in STACS 98 (Paris, 1998), volume 1373 of Lecture Notes in Comput. Sci., pages 332-343. Springer, Berlin, 1998.) | ||||||
| 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. |
||||||
| 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] (Preliminary version in In Automata, languages and programming (Tampere, 1988), volume 317 of Lecture Notes in Comput. Sci., pages 561-575. Springer, Berlin, 1988.) | ||||||
| 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] (Preliminary version in: LATIN '92 (Sao Paulo, 1992), volume 583 of Lecture Notes in Comput. Sci., pages 24-31. Springer, Berlin, 1992. |
||||||
| Richard Beigel and Howard Straubing. The Power of local self-reductions, in Proc. Tenth Annual Conference on Structure in Complexity (Minneapolis 1995). [ps] [pdf] | ||||||
| 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. (Preliminary version in In STACS 89
(Paderborn,
1989), volume 349 of Lecture Notes in Comput. Sci., pages
458-467. Springer, Berlin, 1989.) |
||||||
| 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. |
||||||
| 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. (Preliminary version in
Proceedings ofThirteenth International
Colloquium on Automata, Languages and Programming volume 226 of Lecture
Notes in Comput. Sci., pages 416-423. Springer, Berlin, 1986.
(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. |
||||||
| 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. |