Computer Science Faculty
Howard Straubing
Professor
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
Publications
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, 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). [] (Prelimina