Publications

Last updated March, 2021



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


A. Krebs, K. Lodaya, P. Pandya and H. Straubing, ‘Two-variable logic with betweenness relations: Membership, satisfiability and expressibility’, Logical Methods in Computer Science, 16:3 (2020).

C. Borlido, M. Gehrke, A. Krebs and H. Straubing, ‘Difference hierarchies and duality with an application to formal languages’,  Topology and its Applications 273 (2020).

A. Krebs, K. Lodaya, P. Pandya and H. Straubing, An algebraic decision procedure for two-variable logic with a between relat, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018), 28:1-28:17, (2018).

Howard Straubing, First-order logic and aperiodic languages: A revisionist history, ACM SIGLOG News, 5(3), (2018), 4-20.

Michael Hahn, Andreas Krebs and Howard Straubing, Wreath Products of Distributive Forest Algebras, Proc. 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), (2018), 512-520.

Andreas Krebs and Howard Straubing, An effective characterization of the alternation hierarchy in two-variable logic, ACM Transactions on Computational Logic 18(4:30), (2017).

Arkadev Chattopadhyay, Frederic Green and Howard Straubing, Circuit complexity of powering in fields of odd characteristic, Chicago J. Theor. Comput. Sci. 2016(10), (2016).

Andreas Krebs, Kamal Lodaya, Paritosh Pandya and Howard Straubing, Two-variable logic with a between relation, Proc. 31st ACM/IEEE 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).

, A new proof of the locality of R. International Journal of Algebra and Computation 25 (1-2), 293-300 ()

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.

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.
This file has been generated by bibtex2html 1.66