Computer Science Faculty

Book

• Howard Straubing. Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Birkhäuser Boston Inc., Boston, MA, 1994.

Research and Expository Articles

• Arkadev Chattopadhyay, Frederic Green, Howard Straubing, Circuit complexity of powering in fields of odd characteristic, Chicago J. Theor. Comput. Sci. (2016)
• Andreas Krebs, Kamal Lodaya, Paritosh Pandya and Howard Straubing, Two-variable logic with a between relation, Proc. 27th IEE Symposium on Logic in Computer Science (LICS) (2016), 106-115.
• Andreas Krebs and Howard Straubing, EF+EX forest algebras, in A. Maletti (ed.), Algebraic Informatics, Springer Lecutre Notes in Computer Science 9270, 128-139 (2015).
• Howard Straubing, A new proof of the locality of R. International Journal of Algebra and Computation 25 (1-2), 293-300 (2015)
• Howard Straubing, New applications of the wreath product of forest algebras, RAIRO - Theoretical Informatics and Applications 47(3), 261 - 291 (2013)
• Andreas Krebs and Howard Straubing,  An effective characterization of the alternation hierarchy in two-variable logic. FSTTCS 2012: 86-98
• Mikolaj Bojanczyk, Howard Straubing, and Igor Walukiewicz, Wreath prodcucts of forest algebras, with applications to tree logics,  Logical Methods in Computer Science 8 (3:19), 38pp. (2012). (An extended abstract was published in Proc. 24th IEEE Symposium on Logic in Computer Science (LICS) (2009) 255-263.)
• Mikolaj Bojanczyk, Luc Segoufin and Howard Straubing, Piecewise testable forest languages,  Logical Methods in Computer Science 8 (3:26), 32pp. (2012)  (An extended abstract was prublished in Proc. 23rd IEEE Symposium on Logic in Computer Science (LICS) (2008) 442-451.)
• Howard Straubing and Pascal Weil. An introduction to finite automata and their connection to logic, in Modern applications of automata theory (D. D'Souza, Priti Shankar eds), IISc Research Monographs 2, World Scientific (2012), pp. 3-43. 
• Howard Straubing, Algebraic Characerization of the Alternation Hierarchy in FO2[<] on Finite Words, in Computer Science Logic 2011, LIPIcs 12 (2011) 525-537.  [pdf]
• Howard Straubing, Pascal Tesson and Denis Thérien, Weakly iterated block products and applications to logic and complexity, International Journal of Algebra and Computation, 20(2) 319-341 (2010).
• Howard  Straubing and Denis Thérien,  Modular Quantifiers , in E. Grädel, J. Flum and T. Wilke (eds.), Logic and Automata: History and Perspectives, vol. 2 of the series Texts in Logic and Games, Amsterdam University Press, 2008, pp. 613-628. [pdf]
• Amitabha Roy and Howard Straubing, Definability of languages by generalized first-order formulas over (N,+), in SIAM J. Computing, 37(2)  502–521, (2007). [pdf] (Preliminary version appeared in Proc. 23rd STACS, LNCS 3884 (2006), 35-50.)  
• 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.