Conference item
On the expressiveness of Büchi arithmetic
- Abstract:
- We show that the existential fragment of B¨uchi arithmetic is strictly less expressive than full B¨uchi arithmetic of any base, and moreover establish that its Σ2-fragment is already expressively complete. Furthermore, we show that regular languages of polynomial growth are definable in the existential fragment of B¨uchi arithmetic.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 379.2KB, Terms of use)
-
- Publisher copy:
- 10.1007/978-3-030-71995-1
- Publication website:
- https://www.springer.com/gp/book/9783030719944
Authors
- Publisher:
- Springer
- Host title:
- Foundations of Software Science and Computation Structures: 24th International Conference (FOSSACS 2021). Series Volume 12650.
- Journal:
- Lecture Notes in Computer Science More from this journal
- Pages:
- 310-323
- Series:
- Theoretical Computer Science and General Issues
- Publication date:
- 2021-04-01
- Acceptance date:
- 2020-12-23
- Event title:
- FoSSaCS 2021: 24th International Conference on Foundations of Software Science and Computation Structures
- Event series:
- European Joint Conferences on Theory and Practice of Software
- Event location:
- Online
- Event website:
- https://etaps.org/2021/fossacs
- Event start date:
- 2021-03-27
- Event end date:
- 2021-04-01
- DOI:
- ISSN:
-
0302-9743
- EISBN:
- 978-3-030-71995-1
- ISBN:
- 978-3-030-71994-4
- Language:
-
English
- Keywords:
- Pubs id:
-
1167920
- Local pid:
-
pubs:1167920
- Deposit date:
-
2021-03-15
- ARK identifier:
Terms of use
- Copyright holder:
- C Haase and J Różycki
- Copyright date:
- 2021
- Rights statement:
- © The Authors 2021. Open Access: This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made. The images or other third party material in this chapter are included in the chapter’s Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter’s Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record