Infinitary tree languages recognized by \(\omega\)-automata
type: Item
instance of: scholarly article
title: Infinitary tree languages recognized by \(\omega\)-automata
zbMATH Open document ID: 0539.68072
DOI: 10.1016/0020-0190(84)90068-1
published in: Information Processing Letters
publication date: 1984-01-01T00:00:00Z
review text: Regular nondeterministic program schemata and the closely related regular tree languages in Nivat's sense are characterized by top-down infinite tree automata. Deterministic \(\omega\)-languages form a proper subclass of the recognizable infinitary tree languages and this gap cannot be bridged by taking the Boolean closure.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q60
zbMATH DE Number: 3858447
zbMATH Keywords: deterministic omega-languages
zbMATH Keywords: Rabin's special automata
zbMATH Keywords: Büchi's automata
zbMATH Keywords: regular recursive program schemata
zbMATH Keywords: Regular nondeterministic program schemata
zbMATH Keywords: regular tree languages
zbMATH Keywords: top-down infinite tree automata
zbMATH Keywords: recognizable infinitary tree languages
author: Ahmed Saoudi
reviewed by: Markus Kunze
MaRDI profile type: Publication
full work available at URL: 0020-0190(84)90068-1
OpenAlex ID: W1987994907
cites work: Formal computations of non deterministic recursive program schemes
cites work: Adherences of languages
cites work: Q5517677
cites work: A representation of trees by languages. II
cites work: Q3948612
cites work: A note on infinite trees
cites work: Q3738547
cites work: Q3857704
cites work: Q5616162
cites work: Decidability of Second-Order Theories and Automata on Infinite Trees
description: scientific article; zbMATH DE number 3858447