The Library
Alternating weak automata from universal trees
Tools
Tools
Tools
Daviaud, Laure, Jurdzinski, Marcin and Lehtinen, Karolina (2019) Alternating weak automata from universal trees. In: 30th International Conference on Concurrency Theory (CONCUR 2019) , Amsterdam, the Netherlands, 26-31 Aug 2019. Published in: 30th International Conference on Concurrency Theory (CONCUR 2019), 140 pp. 1-14. ISBN 9783959771214 . doi:10.4230/LIPIcs.CONCUR.2019.18
|
PDF
WRAP-alternating-weak-automata-universal-trees-Jurdzinski-2019.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (446Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.CONCUR.2019.18
Abstract
An improved translation from alternating parity automata on infinite words to alternating weak automata is given. The blow-up of the number of states is related to the size of the smallest universal ordered trees and hence it is quasi-polynomial, and it is polynomial if the asymptotic number of priorities is at most logarithmic in the number of states. This is an exponential improvement on the translation of Kupferman and Vardi (2001) and a quasi-polynomial improvement on the translation of Boker and Lehtinen (2018). Any slightly better such translation would (if - like all presently known such translations - it is efficiently constructive) lead to algorithms for solving parity games that are asymptotically faster in the worst case than the current state of the art (Calude, Jain, Khoussainov, Li, and Stephan, 2017; Jurdzinski and Lazic, 2017; and Fearnley, Jain, Schewe, Stephan, and Wojtczak, 2017), and hence it would yield a significant breakthrough.
| Item Type: | Conference Item (Paper) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > TJ Mechanical engineering and machinery |
|||||||||
| Divisions: | Faculty of Science > Computer Science | |||||||||
| Library of Congress Subject Headings (LCSH): | Machine theory, Robots, Algorithms | |||||||||
| Journal or Publication Title: | 30th International Conference on Concurrency Theory (CONCUR 2019) | |||||||||
| Publisher: | Dagstuhl | |||||||||
| ISBN: | 9783959771214 | |||||||||
| Official Date: | 2019 | |||||||||
| Dates: |
|
|||||||||
| Date of first compliant deposit: | 5 July 2019 | |||||||||
| Volume: | 140 | |||||||||
| Page Range: | pp. 1-14 | |||||||||
| Article Number: | 18 | |||||||||
| DOI: | 10.4230/LIPIcs.CONCUR.2019.18 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Open Access | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Conference Paper Type: | Paper | |||||||||
| Title of Event: | 30th International Conference on Concurrency Theory (CONCUR 2019) | |||||||||
| Type of Event: | Conference | |||||||||
| Location of Event: | Amsterdam, the Netherlands | |||||||||
| Date(s) of Event: | 26-31 Aug 2019 | |||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
