Determinacy of sinking automata on infinite trees and inequalities between various Rabin's pair indices

DOI10.1016/0020-0190(82)90097-7MaRDI QIDQ1068544zbMATH OpenOpenAlexFDO

Authors A. Włodzimierz Mostowski

Publication date 1982

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(82)90097-7

zbMATH Keywords

deterministic sinking automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

Let a set of infinite trees be accepted by an automaton. We prove that then a deterministic sinking automaton accepting the set can be effectively constructed.

Cites work

• Decidability of Second-Order Theories and Automata on Infinite Trees
• Generalized finite automata theory with an application to a decision problem of second-order logic
• scientific article; zbMATH DE number 3735789 (Why is no real title available?)
• scientific article; zbMATH DE number 3358465 (Why is no real title available?)
• On ω-regular sets
• Testing and generating infinite sequences by a finite automaton

Cited in

(6)

• Codeterministic automata on infinite words
• Generalized automata on infinite trees and Muller-McNaughton's theorem
• Unambiguous Büchi automata.
• Automata on infinite trees
• scientific article; zbMATH DE number 3983141 (Why is no real title available?)
• Automata on infinite objects and their applications to logic and programming

This page was built for publication: Determinacy of sinking automata on infinite trees and inequalities between various Rabin's pair indices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1068544)