Howard Straubing

CoRR, 2022

2021

Varieties.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Automata Theory., 2021

2020

Two-variable logics with some betweenness relations: Expressiveness, satisfiability and membership.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2020

2018

First-order logic and aperiodic languages: a revisionist history.

[BibT_eX]

[DOI]

ACM SIGLOG News, 2018

Difference hierarchies and duality with an application to formal languages.

[BibT_eX]

[DOI]

CoRR, 2018

Forest Categories.

[BibT_eX]

[DOI]

CoRR, 2018

Wreath Products of Distributive Forest Algebras.

[BibT_eX]

[DOI]

Michael Hahn

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

An Algebraic Decision Procedure for Two-Variable Logic with a Between Relation.

[BibT_eX]

[DOI]

Proceedings of the 27th EACSL Annual Conference on Computer Science Logic, 2018

2017

An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2017

2016

Two-variable Logic with a Between Predicate.

[BibT_eX]

[DOI]

CoRR, 2016

Circuit Complexity of Powering in Fields of Odd Characteristic.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Frederic Green

Chic. J. Theor. Comput. Sci., 2016

Two-variable Logic with a Between Relation.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

2015

A new proof of the locality of R.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 2015

Varieties.

[BibT_eX]

[DOI]

CoRR, 2015

EF+EX Forest Algebras.

[BibT_eX]

[DOI]

Proceedings of the Algebraic Informatics - 6th International Conference, 2015

2013

New applications of the wreath product of forest algebras.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2013

2012

Wreath Products of Forest Algebras, with Applications to Tree Logics

[BibT_eX]

[DOI]

Mikolaj Bojanczyk

Igor Walukiewicz

Log. Methods Comput. Sci., 2012

Piecewise testable tree languages

[BibT_eX]

[DOI]

Mikolaj Bojanczyk

Luc Segoufin

Log. Methods Comput. Sci., 2012

An Introduction to Finite Automata and their Connection to Logic.

[BibT_eX]

[DOI]

Proceedings of the Modern Applications of Automata Theory., 2012

2011

Algebraic Characterization of the Alternation Hierarchy in FO2[<] on Finite Words.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 2011

2010

Weakly Iterated Block Products and Applications to Logic and Complexity.

[BibT_eX]

[DOI]

Pascal Tesson

Int. J. Algebra Comput., 2010

An introduction to finite automata and their connection to logic

[BibT_eX]

[DOI]

CoRR, 2010

2008

Modular quantifiers.

[BibT_eX]

Proceedings of the Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]., 2008

2007

Definability of Languages by Generalized First-Order Formulas over N+.

[BibT_eX]

[DOI]

Amitabha Roy

SIAM J. Comput., 2007

2006

Actions, wreath products of C-varieties and concatenation product.

[BibT_eX]

[DOI]

Laura Chaubard

Theor. Comput. Sci., 2006

A Note on MODp - MODm Circuits.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2006

Definability of Languages by Generalized First-Order Formulas over (N, +).

[BibT_eX]

[DOI]

Amitabha Roy

Proceedings of the STACS 2006, 2006

First Order Formulas with Modular Predicates.

[BibT_eX]

[DOI]

Laura Chaubard

Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 2006

2005

Some results on C-varieties.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2005

Inexpressibility Results for Regular Languages in Nonregular Settings.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 9th International Conference, 2005

2003

Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2003

2002

Weakly Iterated Block Products of Finite Monoids.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2002: Theoretical Informatics, 2002

On Logical Descriptions of Regular Languages.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2002: Theoretical Informatics, 2002

2001

Languages Defined with Modular Counting Quantifiers.

[BibT_eX]

[DOI]

Inf. Comput., 2001

Characterizations of Regular Languages in Low Level Complexity Classes.

[BibT_eX]

Kevin J. Compton

Proceedings of the Current Trends in Theoretical Computer Science, 2001

1999

Lower bounds for modular counting by circuits with modular gates.

[BibT_eX]

[DOI]

Comput. Complex., 1999

1998

Languages Defined With Modular Counting Quantifiers (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the STACS 98, 1998

1997

Finite Semigroup Varieties Defined by Programs.

[BibT_eX]

[DOI]

Pierre Péladeau

Theor. Comput. Sci., 1997

1996

Finite Models, Automata, and Circuit Complexity.

[BibT_eX]

[DOI]

Proceedings of the Descriptive Complexity and Finite Models, 1996

1995

Regular Languages Defined with Generalized Quanifiers

[BibT_eX]

[DOI]

Wolfgang Thomas

Inf. Comput., May, 1995

Superlinear Lower Bounds for Bounded-Width Branching Programs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1995

The Power of Local Self-Reductions

[BibT_eX]

[DOI]

Richard Beigel

Electron. Colloquium Comput. Complex., 1995

1994

Complex Polynomials and Circuit Lower Bounds for Modular Counting.

[BibT_eX]

[DOI]

Comput. Complex., 1994

1992

Some Results on the Generalized Star-Height Problem

[BibT_eX]

[DOI]

Inf. Comput., December, 1992

On a Conjecture Concerning Dot-Depth Two Languages.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1992

Regular Languages in NC¹.

[BibT_eX]

[DOI]

Kevin J. Compton

J. Comput. Syst. Sci., 1992

Characterizations of regular languages in low level complexity classes.

[BibT_eX]

Kevin J. Compton

Bull. EATCS, 1992

Circuit Complexity and the Expressive Power of Generalized First-Order Formulas.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

1991

Constant-Depth periodic Circuits.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 1991

1990

Non-Uniform Automata Over Groups

[BibT_eX]

[DOI]

Inf. Comput., December, 1990

On Uniformity within NC¹.

[BibT_eX]

[DOI]

Neil Immerman

J. Comput. Syst. Sci., 1990

1989

New Results on the Generalized Star-Height Problem.

[BibT_eX]

[DOI]

Proceedings of the STACS 89, 1989

1988

Semigroups and Languages of Dot-Depth Two.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1988

Finite automata and computational complexity.

[BibT_eX]

[DOI]

Proceedings of the Formal Properties of Finite Automata and Applications, 1988

The wreath product and its applications.

[BibT_eX]

[DOI]

Proceedings of the Formal Properties of Finite Automata and Applications, 1988

regular Languages Defined with Generalized Quantifiers.

[BibT_eX]

[DOI]

Wolfgang Thomas

Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

On uniformity within NC1.

[BibT_eX]

[DOI]

Neil Immerman

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987

Applications of the theory of automata in enumeration.

[BibT_eX]

[DOI]

Discret. Math., 1987

1986

Semigroups and Languages of Dot-Depth 2.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

1983

A combinatorial proof of the Cayley-Hamilton theorem.

[BibT_eX]

[DOI]

Discret. Math., 1983

1981

A Generalization of the Schützenberger Product of Finite Monoids.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1981

Relationals Morphisms and Operations on Recognizable Sets.

[BibT_eX]

[DOI]