Conference item icon

Conference item

The logical strength of Büchi's decidability theorem

Abstract:

We study the strength of axioms needed to prove various results related to automata on infinite words and Büchi's theorem on the decidability of the MSO theory of (N, less_or_equal). We prove that the following are equivalent over the weak second-order arithmetic theory RCA: 1. Büchi's complementation theorem for nondeterministic automata on infinite words, 2. the decidability of the depth-n fragment of the MSO theory of (N, less_or_equal), for each n greater than 5, 3. the induction scheme f...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.CSL.2016.36

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Department:
Unknown
Role:
Author
Publisher:
Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik
Host title:
Leibniz International Proceedings in Informatics, LIPIcs
Journal:
Leibniz International Proceedings in Informatics, LIPIcs More from this journal
Volume:
62
Pages:
36:1-36:16
Publication date:
2016-08-25
Acceptance date:
2016-06-14
DOI:
ISSN:
1868-8969
ISBN:
9783959770224
Keywords:
Pubs id:
pubs:1069610
UUID:
uuid:d385a0ff-edd2-43cb-9d4e-253369e5afbe
Local pid:
pubs:1069610
Source identifiers:
1069610
Deposit date:
2020-01-07

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP