Author name cluster

W. Thomas

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.

1 paper

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