Computer Science Faculty

Howard Straubing

Professor

Photo of Howard Straubing

Howard Straubing

Ph.D.

Contact

245 Beacon Street 507

Telephone: 617-552-3977

Email: howard.straubing@bc.edu

Education

  • A.B., University of Michigan
  • Ph.D., University of California at Berkeley

Courses

Research Interests

Theory of computation, particularly the connections among logic, automata and computational complexity. His current research projects involve algebraic and model-theoretic approaches to circuit complexity and to automata operating on unranked trees.

Department

Computer Science

Publications

Book

  • Howard Straubing.聽Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Birkh盲user 艾可直播 Inc., 艾可直播, 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, s, RAIRO - Theoretical Informatics and Applications 47(3), 261 - 291 (2013)
  • Andreas Krebs and Howard Straubing, 聽. FSTTCS 2012: 86-98
  • Mikolaj Bojanczyk, Howard Straubing, and Igor Walukiewicz, , 聽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, , 聽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. 聽[]
  • 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. []
  • Amitabha Roy and Howard Straubing, Definability of languages by generalized first-order formulas over (N,+), in SIAM J. Computing, 37(2) 聽502鈥�521, (2007). [] (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. []
  • 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. []
  • 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. []
  • Eduardo Duenez, Steven Miller, Amitabha Roy and Howard Straubing. Incomplete Quadratic Exponential Sums in Several Variables. J. Number Theory, 116 (2006) 168-199. []
  • 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). []
  • 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. [] [] 聽(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. []
  • 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. [] 聽 []
  • 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. [] 聽[]
  • 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. [] 聽 [] 聽 (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 艾可直播, 艾可直播, MA, 2000. [] []
  • 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. [] []
  • 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). [] []
  • Howard Straubing, Denis Th茅rien, and Wolfgang Thomas. Regular languages defined with generalized quantifiers. Inform. and Comput., 118(2):289-301, 1995. [] [] 聽(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). [] [] (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). [] 聽[
  • 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.
Back To Top