Author name cluster

H. 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.

3 papers

1 author row

I&C Journal 1995 Journal Article

Regular Languages Defined with Generalized Quantifiers

H. Straubing
D. Therien
W. Thomas

We study an extension of first-order logic obtained by adjoining quantifiers that count with respect to an integer modulus. It is shown that the languages definable in this framework are precisely the regular languages whose syntactic monoids contain only solvable groups. We obtain an analogous result for regular ω-languages and establish some connections with complexity theory for fixed-depth families of circuits.

Details DOI

TCS Journal 1992 Journal Article

On a conjecture concerning dot-depth two languages

H. Straubing
P. Weil

In this paper, we study the second level of the dot-depth hierarchy for star-free regular languages. We investigate a necessary condition stated by Straubing for a language to have dot-depth two, and prove that it is sufficient for languages whose syntactic monoid is inverse with three inverse generators. Also we disprove a conjecture according to which Straubing's condition would be equivalent to both dot-depth two and another condition expressed in terms of two-sided semidirect product.

Details DOI

I&C Journal 1992 Journal Article

Some results on the generalized star-height problem

J.E. Pin
H. Straubing
D. Thérien

We prove some results related to the generalized star-height problem. In this problem, as opposed to the restricted star-height problem, complementation is considered as a basic operator. We first show that the class of languages of star-height ≤ n is closed under certain operations (left and right quotients, inverse alphabetic morphisms, injective star-free substitutions). It is known that languages recognized by a commutative group are of star-height 1. We extend this result to nilpotent groups of class 2 and to the groups that divide a semidirect product of a commutative group by ( Z /2 Z ) n. In the same direction, we show that one of the languages that were conjectured to be of star-height 2 during the past ten years is in fact of star-height 1. Next we show that if a rational language L is recognized by a monoid of the variety generated by wreath products of the form M ∘ (G ∘ N), where M and N are aperiodic monoids, and G is a commutative group, the L is of star-height ≤ 1. Finally we show that every rational language is the inverse image, under some morphism between free monoids, of a language of (resticted) star-height 1.

Details DOI