Recognisability for algebras of infinite trees (Q551167): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Magnus Steinby / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q70 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 08A70 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03B70 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 5920425 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
infinite trees | |||
Property / zbMATH Keywords: infinite trees / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
tree automata | |||
Property / zbMATH Keywords: tree automata / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
recognizable sets | |||
Property / zbMATH Keywords: recognizable sets / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
formal languages | |||
Property / zbMATH Keywords: formal languages / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
monadic second-order logic | |||
Property / zbMATH Keywords: monadic second-order logic / rank | |||
Normal rank |
Revision as of 13:42, 1 July 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Recognisability for algebras of infinite trees |
scientific article |
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