Transforming structures by set interpretations

Thomas Colcombet; Christof Löding

doi:10.2168/LMCS-3(2:4)2007

Thomas Colcombet ; Christof Löding - Transforming structures by set interpretations

lmcs:2221 - Logical Methods in Computer Science, May 4, 2007, Volume 3, Issue 2 - https://doi.org/10.2168/LMCS-3(2:4)2007

Transforming structures by set interpretationsArticle

Authors: Thomas Colcombet ; Christof Löding

We consider a new kind of interpretation over relational structures: finite sets interpretations. Those interpretations are defined by weak monadic second-order (WMSO) formulas with free set variables. They transform a given structure into a structure with a domain consisting of finite sets of elements of the orignal structure. The definition of these interpretations directly implies that they send structures with a decidable WMSO theory to structures with a decidable first-order theory. In this paper, we investigate the expressive power of such interpretations applied to infinite deterministic trees. The results can be used in the study of automatic and tree-automatic structures.

Comment: 36 pages

https://doi.org/10.2168/LMCS-3(2:4)2007

Source: arXiv.org:cs/0703039

Volume: Volume 3, Issue 2

Published on: May 4, 2007

Imported on: July 18, 2006

Keywords: Computer Science - Logic in Computer Science, F.4.1

Licence: arXiv.org - Assumed non-exclusive license to distribute

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Bibliographic References

22 Documents citing this article

Chih-Duo Hong;Anthony W. Lin;Philipp Rümmer;Rupak Majumdar, 2025, Probabilistic Bisimulation for Parameterized Anonymity and Uniformity Verification, ArXiv.org, 51, 6, pp. 1801-1817, 10.1109/tse.2025.3567423, http://arxiv.org/abs/2505.09963.

Alexsander Andrade de Melo;Mateus de Oliveira Oliveira, 2022, Second-Order Finite Automata, Theory of Computing Systems, 66, 4, pp. 861-909, 10.1007/s00224-022-10085-w, https://doi.org/10.1007/s00224-022-10085-w.

Anthony W. Lin;Philipp Rümmer, 2021, Regular Model Checking Revisited, Lecture notes in computer science, pp. 97-114, 10.1007/978-3-030-91384-7_6.

Michael Benedikt;Pierre Pradic, 2021, Generating collection transformations from proofs, Proceedings of the ACM on Programming Languages, 5, POPL, pp. 1-28, 10.1145/3434295, https://doi.org/10.1145/3434295.

Paweł Parys, 2021, The Caucal hierarchy: Interpretations in the (W)MSO+U logic, Information and Computation, 286, pp. 104782, 10.1016/j.ic.2021.104782.

Erich Grädel, 2020, Automatic Structures, Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 21-34, 10.1145/3373718.3394734.

Chih-Duo Hong;Anthony W. Lin;Rupak Majumdar;Philipp Rümmer, 2019, Probabilistic Bisimulation for Parameterized Systems, Lecture notes in computer science, pp. 455-474, 10.1007/978-3-030-25540-4_27, https://doi.org/10.1007/978-3-030-25540-4_27.

Paweł Parys, 2019, Extensions of the Caucal Hierarchy?, Lecture notes in computer science, pp. 368-380, 10.1007/978-3-030-13435-8_27.

Alexandre Mansard, 2018, Unfolding of Finite Concurrent Automata, Electronic Proceedings in Theoretical Computer Science, 279, pp. 68-84, 10.4204/eptcs.279.8, https://doi.org/10.4204/eptcs.279.8.

Xuan-Bach Le;Aquinas Hobor;Anthony W. Lin, 2018, Complexity Analysis of Tree Share Structure, Lecture notes in computer science, pp. 89-108, 10.1007/978-3-030-02768-1_5.

Vincent Penelle, 2017, Rewriting Higher-Order Stack Trees, Theory of Computing Systems, 61, 2, pp. 536-580, 10.1007/s00224-017-9769-6, https://doi.org/10.1007/s00224-017-9769-6.

Sanjay Jain;Bakhadyr Khoussainov;Philipp Schlicht;Frank Stephan, 2016, Tree-automatic scattered linear orders, Theoretical Computer Science, 626, pp. 83-96, 10.1016/j.tcs.2016.02.008.

Vincent Penelle, 2015, Rewriting Higher-Order Stack Trees, pp. 364-397, 10.1007/978-3-319-20297-6_24, https://hal.science/hal-01117753.

Martin Lang;Christof Löding;Amaldev Manuel, 2014, Definability and Transformations for Cost Logics and Automatic Structures, Lecture notes in computer science, pp. 390-401, 10.1007/978-3-662-44522-8_33.

Alex Kruckman;Sasha Rubin;John Sheridan;Ben Zax, 2012, A Myhill-Nerode theorem for automata with advice, Electronic Proceedings in Theoretical Computer Science, 96, pp. 238-246, 10.4204/eptcs.96.18, https://doi.org/10.4204/eptcs.96.18.

Alexander Rabinovich;Sasha Rubin, 2012, Interpretations in Trees with Countably Many Branches, 2012 27th Annual IEEE Symposium on Logic in Computer Science, 960, pp. 551-560, 10.1109/lics.2012.65.

Achim Blumensath, 2011, Simple monadic theories and partition width, Mathematical logic quarterly, 57, 4, pp. 409-431, 10.1002/malq.201010019.

Dietrich Kuske;Markus Lohrey, 2011, Automatic structures of bounded degree revisited, Journal of Symbolic Logic, 76, 4, pp. 1352-1380, 10.2178/jsl/1318338854.

Dietrich Kuske;Thomas Weidner, 2011, Size and Computation of Injective Tree Automatic Presentations, Lecture notes in computer science, pp. 424-435, 10.1007/978-3-642-22993-0_39.

Barbara F. Csima;Bakhadyr Khoussainov, 2008, When Is Reachability Intrinsically Decidable?, Lecture notes in computer science, pp. 216-227, 10.1007/978-3-540-85780-8_17.

Greg Hjorth;Bakh Khoussainov;Antonio Montalbán;André Nies, 2008, From Automatic Structures to Borel Structures, Proceedings - Symposium on Logic in Computer Science, 217, pp. 431-441, 10.1109/lics.2008.28.

Sasha Rubin, 2008, Automata Presenting Structures: A Survey of the Finite String Case, Bulletin of Symbolic Logic, 14, 2, pp. 169-209, 10.2178/bsl/1208442827.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 3140 times.

This article's PDF has been downloaded 455 times.