First-order logic and star-free sets (Q1088982): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0022-0000(86)90037-1 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2020558489 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The dot-depth hierarchy of star-free languages is infinite / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q5618355 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q5641083 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3718174 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3698327 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3776657 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Finite semigroup varieties of the form V*D / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Star-free regular sets of ω-sequences / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Classifying regular events in symbolic logic / rank | |||
Normal rank | |||
Latest revision as of 18:44, 17 June 2024
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
