Howard Straubing

Publication Activity (10 Years)

Years Active: 1981-2022
Publications (10 Years): 13

Top Topics

Clifford Algebra

Proof Procedure

Formal Language

Top Venues

Chic. J. Theor. Comput. Sci.

ACM SIGLOG News

Publications

Andreas Krebs, Howard Straubing
Regular languages defined by first-order formulas without quantifier alternation. CoRR (2022)
Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing
Two-variable logics with some betweenness relations: Expressiveness, satisfiability and membership. Log. Methods Comput. Sci. 16 (3) (2020)
Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing
Two-variable logics with some betweenness relations: Expressiveness, satisfiability and membership. CoRR (2019)
Michael Hahn, Andreas Krebs, Howard Straubing
Wreath Products of Distributive Forest Algebras. CoRR (2019)
Célia Borlido, Mai Gehrke, Andreas Krebs, Howard Straubing
Difference hierarchies and duality with an application to formal languages. CoRR (2018)
Howard Straubing
First-order logic and aperiodic languages: a revisionist history. ACM SIGLOG News 5 (3) (2018)
Michael Hahn, Andreas Krebs, Howard Straubing
Wreath Products of Distributive Forest Algebras. LICS (2018)
Howard Straubing
Forest Categories. CoRR (2018)
Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing
An Algebraic Decision Procedure for Two-Variable Logic with a Between Relation. CSL (2018)
Andreas Krebs, Howard Straubing
An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic. ACM Trans. Comput. Log. 18 (4) (2017)
Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing
Two-variable Logic with a Between Relation. LICS (2016)
Arkadev Chattopadhyay, Frederic Green, Howard Straubing
Circuit Complexity of Powering in Fields of Odd Characteristic. Chic. J. Theor. Comput. Sci. 2016 (2016)
Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing
Two-variable Logic with a Between Predicate. CoRR (2016)
Howard Straubing, Pascal Weil
Varieties. CoRR (2015)
Howard Straubing
A new proof of the locality of R. Int. J. Algebra Comput. 25 (1-2) (2015)
Andreas Krebs, Howard Straubing
EF+EX Forest Algebras. CAI (2015)
Andreas Krebs, Howard Straubing
EF+EX Forest Algebras. CoRR (2014)
Howard Straubing
New applications of the wreath product of forest algebras. RAIRO Theor. Informatics Appl. 47 (3) (2013)
Mikolaj Bojanczyk, Luc Segoufin, Howard Straubing
Piecewise testable tree languages Log. Methods Comput. Sci. 8 (3) (2012)
Andreas Krebs, Howard Straubing
An effective characterization of the alternation hierarchy in two-variable logic CoRR (2012)
Mikolaj Bojanczyk, Howard Straubing, Igor Walukiewicz
Wreath Products of Forest Algebras, with Applications to Tree Logics Log. Methods Comput. Sci. 8 (3) (2012)
Andreas Krebs, Howard Straubing
An effective characterization of the alternation hierarchy in two-variable logic. FSTTCS (2012)
Howard Straubing
[<] on Finite Words. CSL (2011)
Howard Straubing, Pascal Weil
An introduction to finite automata and their connection to logic CoRR (2010)
Howard Straubing, Pascal Tesson, Denis Thérien
Weakly Iterated Block Products and Applications to Logic and Complexity. Int. J. Algebra Comput. 20 (2) (2010)
Mikolaj Bojanczyk, Howard Straubing, Igor Walukiewicz
Wreath Products of Forest Algebras, with Applications to Tree Logics. LICS (2009)
Howard Straubing, Denis Thérien
Modular quantifiers. Logic and Automata (2008)
Mikolaj Bojanczyk, Luc Segoufin, Howard Straubing
Piecewise Testable Tree Languages. LICS (2008)
Amitabha Roy, Howard Straubing
. SIAM J. Comput. 37 (2) (2007)
Howard Straubing, Denis Thérien
Circuits. Theory Comput. Syst. 39 (5) (2006)
Laura Chaubard, Jean-Eric Pin, Howard Straubing
First Order Formulas with Modular Predicates. LICS (2006)
Laura Chaubard, Jean-Eric Pin, Howard Straubing
-varieties and concatenation product. Theor. Comput. Sci. 356 (1-2) (2006)
Amitabha Roy, Howard Straubing
Definability of Languages by Generalized First-Order Formulas over (N, +). STACS (2006)
Howard Straubing
Inexpressibility Results for Regular Languages in Nonregular Settings. Developments in Language Theory (2005)
Jean-Eric Pin, Howard Straubing
Some results on $\cal C$-varieties. RAIRO Theor. Informatics Appl. 39 (1) (2005)
Howard Straubing, Denis Thérien
Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables. Theory Comput. Syst. 36 (1) (2003)
Howard Straubing, Denis Thérien
Weakly Iterated Block Products of Finite Monoids. LATIN (2002)
Howard Straubing
On Logical Descriptions of Regular Languages. LATIN (2002)
Howard Straubing, Denis Thérien
Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables. STACS (2001)
Howard Straubing
Languages Defined with Modular Counting Quantifiers. Inf. Comput. 166 (2) (2001)
David A. Mix Barrington, Howard Straubing
Lower bounds for modular counting by circuits with modular gates. Comput. Complex. 8 (3) (1999)
Howard Straubing
Languages Defined With Modular Counting Quantifiers (Extended Abstract). STACS (1998)
Pierre Péladeau, Howard Straubing, Denis Thérien
Finite Semigroup Varieties Defined by Programs. Theor. Comput. Sci. 180 (1-2) (1997)
Howard Straubing
Finite Models, Automata, and Circuit Complexity. Descriptive Complexity and Finite Models (1996)
David A. Mix Barrington, Howard Straubing
Lower Bounds for Modular Counting by Circuits with Modular Gates. LATIN (1995)
Richard Beigel, Howard Straubing
The Power of Local Self-Reductions Electron. Colloquium Comput. Complex. 2 (37) (1995)
Richard Beigel, Howard Straubing
The Power of Local Self-Reductions. Computational Complexity Conference (1995)
David A. Mix Barrington, Howard Straubing
Superlinear Lower Bounds for Bounded-Width Branching Programs. J. Comput. Syst. Sci. 50 (3) (1995)
Howard Straubing, Denis Thérien, Wolfgang Thomas
Regular Languages Defined with Generalized Quanifiers Inf. Comput. 118 (2) (1995)
David A. Mix Barrington, Howard Straubing
Complex Polynomials and Circuit Lower Bounds for Modular Counting. Comput. Complex. 4 (1994)
David A. Mix Barrington, Kevin J. Compton, Howard Straubing, Denis Thérien
Regular Languages in NC¹. J. Comput. Syst. Sci. 44 (3) (1992)
David A. Mix Barrington, Howard Straubing
Complex Polynomials and Circuit Lower Bounds for Modular Counting. LATIN (1992)
Jean-Eric Pin, Howard Straubing, Denis Thérien
Some Results on the Generalized Star-Height Problem Inf. Comput. 101 (2) (1992)
Howard Straubing
Circuit Complexity and the Expressive Power of Generalized First-Order Formulas. ICALP (1992)
Kevin J. Compton, Howard Straubing
Characterizations of regular languages in low level complexity classes. Bull. EATCS 48 (1992)
Howard Straubing, Pascal Weil
On a Conjecture Concerning Dot-Depth Two Languages. Theor. Comput. Sci. 104 (2) (1992)
David A. Mix Barrington, Howard Straubing
Superlinear Lower Bounds for Bounded-Width Branching Programs. Computational Complexity Conference (1991)
Howard Straubing
Constant-Depth periodic Circuits. Int. J. Algebra Comput. 1 (1) (1991)
David A. Mix Barrington, Howard Straubing, Denis Thérien
Non-Uniform Automata Over Groups Inf. Comput. 89 (2) (1990)
David A. Mix Barrington, Neil Immerman, Howard Straubing
On Uniformity within NC¹. J. Comput. Syst. Sci. 41 (3) (1990)
Jean-Eric Pin, Howard Straubing, Denis Thérien
New Results on the Generalized Star-Height Problem. STACS (1989)
David A. Mix Barrington, Neil Immerman, Howard Straubing
. Computational Complexity Conference (1988)
Howard Straubing, Denis Thérien
Finite automata and computational complexity. Formal Properties of Finite Automata and Applications (1988)
Howard Straubing, Denis Thérien, Wolfgang Thomas
regular Languages Defined with Generalized Quantifiers. ICALP (1988)
Howard Straubing
Semigroups and Languages of Dot-Depth Two. Theor. Comput. Sci. 58 (1988)
Howard Straubing
The wreath product and its applications. Formal Properties of Finite Automata and Applications (1988)
Howard Straubing
Applications of the theory of automata in enumeration. Discret. Math. 64 (2-3) (1987)
Howard Straubing
Semigroups and Languages of Dot-Depth 2. ICALP (1986)
Howard Straubing
A combinatorial proof of the Cayley-Hamilton theorem. Discret. Math. 43 (2-3) (1983)
Howard Straubing
A Generalization of the Schützenberger Product of Finite Monoids. Theor. Comput. Sci. 13 (1981)
Howard Straubing
Relationals Morphisms and Operations on Recognizable Sets. RAIRO Theor. Informatics Appl. 15 (2) (1981)