First-order logic and star-free sets (Q1088982)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | First-order logic and star-free sets |
scientific article |
Statements
First-order logic and star-free sets (English)
0 references
1986
0 references
In the paper a version of the Thomas theorem on the correspondence between star-free languages and a hierarchy of first-order logic formulas based on the alternation of existential and universal quantifiers is proved. The proof is based on the Straubing hierarchy of aperiodic languages. The main result is generalized to the case of languages with infinite words.
0 references
star-free languages
0 references
hierarchy of first-order logic formulas
0 references
alternation of existential and universal quantifiers
0 references
Straubing hierarchy of aperiodic languages
0 references
languages with infinite words
0 references
