Title: Infinitary tree languages recognized by ω-automata
Abstract: We define top-down infinite tree automata (ω-automata) which is an extension of Rabin's automata to infinite Σ-tress. We prove that each ω-automaton can be completed to an equivalent one and that non-deterministic ω-automata have more power than deterministic ω-automata. We study the difference between ω-languages and deterministic ω-languages by using AFL-like operations.
Publication Year: 1984
Publication Date: 1984-01-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 4
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot