|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Unambiguous Tree Languages Are Topologically Harder Than Deterministic Ones | | Szczepan Hummel
; | | Date: |
9 Oct 2012 | | Abstract: | The paper gives an example of a tree language G that is recognised by an
unambiguous parity automaton and is analytic-complete as a set in Cantor space.
This already shows that the unambiguous languages are topologically more
complex than the deterministic ones, that are all coanalytic.
Using set G as a building block we construct an unambiguous language that is
topologically harder than any countable boolean combination of analytic and
coanalytic sets. In particular the language is harder than any set in
difference hierarchy of analytic sets considered by O.Finkel and P.Simonnet in
the context of nondeterministic automata. | | Source: | arXiv, 1210.2463 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER