Recognisability for algebras of infinite trees (Q551167)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5920425
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Recognisability for algebras of infinite trees |
scientific article; zbMATH DE number 5920425 |
Statements
Recognisability for algebras of infinite trees (English)
0 references
14 July 2011
0 references
The author proposes an algebraic approach to the theory of regular languages of infinite trees that would parallel the classical semigroup-theoretic treatment of regular languages of finite words and the many later theories inspired by it. For this purpose he introduces a suitable class of algebras, called \(\omega\)-hyperclones, and proves then that the sets recognized by a certain special type of such algebras are precisely the regular languages of infinite trees. Furthermore, he presents some closure properties of these algebras from which the equivalence of recognizability and second-order definability also follows.
0 references
infinite trees
0 references
tree automata
0 references
recognizable sets
0 references
formal languages
0 references
monadic second-order logic
0 references
0.8769978880882263
0 references
0.8361127376556396
0 references
0.8162668347358704
0 references
0.8024618029594421
0 references
