Ambiguity of {\omega}-Languages of Turing Machines
An {\omega}-language is a set of infinite words over a finite alphabet X. We consider the class of recursive {\omega}-languages, i.e. the class of {\omega}-languages accepted by Turing machines with a B\"uchi acceptance condition, which is also the class {\Sigma}11 of (effective) analytic subse...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2014-08-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/765/pdf |
| _version_ | 1797268666794901504 |
|---|---|
| author | Olivier Finkel |
| author_facet | Olivier Finkel |
| author_sort | Olivier Finkel |
| collection | DOAJ |
| description | An {\omega}-language is a set of infinite words over a finite alphabet X. We
consider the class of recursive {\omega}-languages, i.e. the class of
{\omega}-languages accepted by Turing machines with a B\"uchi acceptance
condition, which is also the class {\Sigma}11 of (effective) analytic subsets
of X{\omega} for some finite alphabet X. We investigate here the notion of
ambiguity for recursive {\omega}-languages with regard to acceptance by B\"uchi
Turing machines. We first present in detail essentials on the literature on
{\omega}-languages accepted by Turing Machines. Then we give a complete and
broad view on the notion of ambiguity and unambiguity of B\"uchi Turing
machines and of the {\omega}-languages they accept. To obtain our new results,
we make use of results and methods of effective descriptive set theory. |
| first_indexed | 2024-04-25T01:36:07Z |
| format | Article |
| id | doaj.art-ecb94799b543448184752bee36f55fdf |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:36:07Z |
| publishDate | 2014-08-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-ecb94799b543448184752bee36f55fdf2024-03-08T09:37:13ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742014-08-01Volume 10, Issue 310.2168/LMCS-10(3:12)2014765Ambiguity of {\omega}-Languages of Turing MachinesOlivier FinkelAn {\omega}-language is a set of infinite words over a finite alphabet X. We consider the class of recursive {\omega}-languages, i.e. the class of {\omega}-languages accepted by Turing machines with a B\"uchi acceptance condition, which is also the class {\Sigma}11 of (effective) analytic subsets of X{\omega} for some finite alphabet X. We investigate here the notion of ambiguity for recursive {\omega}-languages with regard to acceptance by B\"uchi Turing machines. We first present in detail essentials on the literature on {\omega}-languages accepted by Turing Machines. Then we give a complete and broad view on the notion of ambiguity and unambiguity of B\"uchi Turing machines and of the {\omega}-languages they accept. To obtain our new results, we make use of results and methods of effective descriptive set theory.https://lmcs.episciences.org/765/pdfcomputer science - logic in computer sciencecomputer science - computational complexitymathematics - logic |
| spellingShingle | Olivier Finkel Ambiguity of {\omega}-Languages of Turing Machines Logical Methods in Computer Science computer science - logic in computer science computer science - computational complexity mathematics - logic |
| title | Ambiguity of {\omega}-Languages of Turing Machines |
| title_full | Ambiguity of {\omega}-Languages of Turing Machines |
| title_fullStr | Ambiguity of {\omega}-Languages of Turing Machines |
| title_full_unstemmed | Ambiguity of {\omega}-Languages of Turing Machines |
| title_short | Ambiguity of {\omega}-Languages of Turing Machines |
| title_sort | ambiguity of omega languages of turing machines |
| topic | computer science - logic in computer science computer science - computational complexity mathematics - logic |
| url | https://lmcs.episciences.org/765/pdf |
| work_keys_str_mv | AT olivierfinkel ambiguityofomegalanguagesofturingmachines |