Recognisability for algebras of infinite trees (Q551167): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
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 | |||
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/j.tcs.2011.02.037 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2011892490 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3615303 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algebra for Infinite Forests with an Application to the Temporal Logic EF / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3086921 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2770673 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Characterizing CTL-like logics on finite trees. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algebraic recognizability of regular tree languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: ALGEBRAIC CHARACTERIZATION OF LOGICALLY DEFINED TREE LANGUAGES / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5317419 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Positive varieties of tree languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Tree algebras and varieties of tree languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4273660 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: General varieties of tree languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algebras for classifying regular tree languages and an application to frontier testability / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 07:30, 4 July 2024
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