Determinacy of sinking automata on infinite trees and inequalities between various Rabin's pair indices (Q1068544): Difference between revisions

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.

0 references

Mathematics Subject Classification ID

68Q45

0 references

zbMATH DE Number

3932393

0 references

zbMATH Keywords

deterministic sinking automaton

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0020-0190(82)90097-7

0 references

OpenAlex ID

W2167227381

0 references

cites work

Testing and generating infinite sequences by a finite automaton

0 references

Q3922660

0 references

Decidability of Second-Order Theories and Automata on Infinite Trees

0 references

Q5632564

0 references

Generalized finite automata theory with an application to a decision problem of second-order logic

0 references

On ω-regular sets

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1068544

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0020-0190(82)90097-7
+Normal rank
@@ Property / OpenAlex ID @@
+W2167227381
@@ Property / OpenAlex ID: W2167227381 / rank @@
+Normal rank
@@ Property / cites work @@
+Testing and generating infinite sequences by a finite automaton
+Normal rank
@@ Property / cites work @@
+Q3922660
@@ Property / cites work: Q3922660 / rank @@
+Normal rank
@@ Property / cites work @@
+Decidability of Second-Order Theories and Automata on Infinite Trees
+Normal rank
@@ Property / cites work @@
+Q5632564
@@ Property / cites work: Q5632564 / rank @@
+Normal rank
@@ Property / cites work @@
+Generalized finite automata theory with an application to a decision problem of second-order logic
+Normal rank
@@ Property / cites work @@
+On ω-regular sets
@@ Property / cites work: On ω-regular sets / rank @@
+Normal rank