The Emptiness Problem for Automata on Infinite Trees
The purpose of this paper is to give an alternative proof to the decidability of the emptiness problem for tree automata, as shown in Rabin [4]. The proof reduces the emptiness problem for automata on infinite trees to that for automata on finite trees, by showing that any automata definable set of...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148858 |
| _version_ | 1811077982821810176 |
|---|---|
| author | Hossley, Robert Rackoff, Charles |
| author_facet | Hossley, Robert Rackoff, Charles |
| author_sort | Hossley, Robert |
| collection | MIT |
| description | The purpose of this paper is to give an alternative proof to the decidability of the emptiness problem for tree automata, as shown in Rabin [4]. The proof reduces the emptiness problem for automata on infinite trees to that for automata on finite trees, by showing that any automata definable set of infinite trees must contain a finitely-genarable trees. |
| first_indexed | 2024-09-23T10:51:32Z |
| id | mit-1721.1/148858 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:51:32Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1488582023-03-30T03:58:36Z The Emptiness Problem for Automata on Infinite Trees Hossley, Robert Rackoff, Charles The purpose of this paper is to give an alternative proof to the decidability of the emptiness problem for tree automata, as shown in Rabin [4]. The proof reduces the emptiness problem for automata on infinite trees to that for automata on finite trees, by showing that any automata definable set of infinite trees must contain a finitely-genarable trees. 2023-03-29T14:02:56Z 2023-03-29T14:02:56Z 1972-06 https://hdl.handle.net/1721.1/148858 09913094 MIT-LCS-TM-029 MAC-TM-029 application/pdf |
| spellingShingle | Hossley, Robert Rackoff, Charles The Emptiness Problem for Automata on Infinite Trees |
| title | The Emptiness Problem for Automata on Infinite Trees |
| title_full | The Emptiness Problem for Automata on Infinite Trees |
| title_fullStr | The Emptiness Problem for Automata on Infinite Trees |
| title_full_unstemmed | The Emptiness Problem for Automata on Infinite Trees |
| title_short | The Emptiness Problem for Automata on Infinite Trees |
| title_sort | emptiness problem for automata on infinite trees |
| url | https://hdl.handle.net/1721.1/148858 |
| work_keys_str_mv | AT hossleyrobert theemptinessproblemforautomataoninfinitetrees AT rackoffcharles theemptinessproblemforautomataoninfinitetrees AT hossleyrobert emptinessproblemforautomataoninfinitetrees AT rackoffcharles emptinessproblemforautomataoninfinitetrees |