Author name cluster

Howard Straubing

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

2 author rows

CSL Conference 2018 Conference Paper

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

Andreas Krebs
Kamal Lodaya
Paritosh K. Pandya
Howard Straubing

In earlier work (LICS 2016), the authors introduced two-variable first-order logic supplemented by a binary relation that allows one to say that a letter appears between two positions. We found an effective algebraic criterion that is a necessary condition for definability in this logic, and conjectured that the criterion is also sufficient, although we proved this only in the case of two-letter alphabets. Here we prove the general conjecture. The proof is quite different from the arguments in the earlier work, and required the development of novel techniques concerning factorizations of words. We extend the results to binary relations specifying that a factor appears between two positions.

Details

CSL Conference 2011 Conference Paper

Algebraic Characterization of the Alternation Hierarchy in FO 2 [<] on Finite Words

Howard Straubing

We give an algebraic characterization of the quantifier alternation hierarchy in first-order two-variable logic on finite words. As a result, we obtain a new proof that this hierarchy is strict. We also show that the first two levels of the hierarchy have decidable membership problems, and conjecture an algebraic decision procedure for the other levels.

Details

TCS Journal 2006 Journal Article

Actions, wreath products of C -varieties and concatenation product

Laura Chaubard
Jean-Éric Pin
Howard Straubing

The framework of C -varieties, introduced by the third author, extends the scope of Eilenberg's variety theory to new classes of languages. In this paper, we first define C -varieties of actions, which are closely related to automata, and prove their equivalence with the original definition of C -varieties of stamps. Next, we complete the study of the wreath product initiated by Ésik and Ito by extending its definition to C -varieties in two different ways, which are proved to be equivalent. We also state an extension of the wreath product principle, a standard tool of language theory. Finally, our main result generalizes to C -varieties the algebraic characterization of the closure under product of a variety of languages.

Details DOI

I&C Journal 2001 Journal Article

Languages Defined with Modular Counting Quantifiers

Howard Straubing

We prove that a regular language defined by a boolean combination of generalized Σ1-sentences built using modular counting quantifiers can be defined by a boolean combination of Σ1-sentences in which only regular numerical predicates appear. The same statement, with “Σ1” replaced by “first-order, ” is equivalent to the conjecture that the nonuniform circuit complexity class ACC is strictly contained in NC 1. The argument introduces some new techniques, based on a combination of semigroup theory and Ramsey theory, which may shed some light on the general case.

Details DOI

TCS Journal 1997 Journal Article

Finite semigroup varieties defined by programs

Pierre Péladeau
Howard Straubing
Denis Therien

We study the regular languages recognized by polynomial-length programs over finite semigroups belonging to product varieties V ∗ LI, where V is a variety of finite monoids, and LI is the variety of finite locally trivial semigroups. In the case where the semigroup variety has a particular closure property with respect to programs, we are able to give precise characterizations of these regular languages. As a corollary we obtain new proofs of the results of Barrington, Compton, Straubing and Therien characterizing the regular languages in certain circuit complexity classes.

Details DOI

I&C Journal 1990 Journal Article

Non-uniform automata over groups

David A. Mix Barrington
Howard Straubing
Denis Thérien

A new model, non-uniform deterministic finite automata (NUDFA's) over general finite monoids, has recently been developed as a strong link between the theory of finite automata and low-level parallel complexity. Achievements of this model include the proof that width 5 branching programs recognize exactly the languages in non-uniform NC 1, NUDFA characterizations of several important subclasses of NC 1, and a new proof of the old result that the dot-dephth hierarchy is infinite, using M. Sipser's (1983, in “Proceedings, 15th ACM Symposium on the Theory of Computing, ” Association for Computing Machinery, New York, pp. 61–69) work on constant depth circuits. Here we extend this theory to NUDFA's over solvable groups (NUDFA's over non-solvable groups have the maximum possible computing power). We characterize the power of NUDFA's over nilpotent groups and prove some optimal lower bounds for NUDFA's over certain groups which are solvable but not nilpotent. Most of these results appeared in preliminary form in (D. A. Barrington and D. Thérien, 1987, in “Automata, Languages, and Programming: 14th International Colloquium, ” Springer-Verlag, Berlin, pp. 163–173).

Details DOI

TCS Journal 1988 Journal Article

Semigroups and languages of dot-depth two

Howard Straubing

This paper is a contribution to the problem of effectively determining the dot-depth of a star-free language, a problem concerning formal languages that has close connections to semigroup theory and mathematical logic. I conjecture an effective criterion, based on the syntactic monoid of the language, for determining whether a given language has dot-depth two, and prove the conjecture in the case of languages over an alphabet of two letters. The condition is formulated in terms of a novel use of categories in semigroup theory, recently developed by Tilson.

Details DOI

TCS Journal 1981 Journal Article

A generalization of the Schützenberger product of finite monoids

Howard Straubing

For each n⩾1, an n-ary product ♢ on finite monoids is constructed. This product has the following property: Let Σ be a finite alphabet and Σ∗ the free monoid generated by Σ. For i = 1, …, n, let Ai be a recognizable subset of Σ∗, M(Ai ) the syntactic monoid of An and M(A 1⋯An ) the syntactic monoid of the concatenation product A 1⋯An. Then M(A 1⋯A n )< ♢ (M(A 1), …, M(A n )). The case n = 2 was studied by Schützenberger. As an application of the generalized product, I prove the theorem of Brzozowski and Knast that the dot-depth hierarchy of star-free sets is infinite.

Details DOI