Top

Published in:

2019 | OriginalPaper | Chapter

Extensions of the Caucal Hierarchy?

Author : Paweł Parys

Published in: Language and Automata Theory and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The Caucal hierarchy contains graphs that can be obtained from finite graphs by alternately applying the unfolding operation and inverse rational mappings. The goal of this work is to check whether the hierarchy is closed under interpretations in logics extending the monadic second-order logic by the unbounding quantifier \(\mathsf U\). We prove that by applying interpretations described in the MSO+\(\mathsf {U^{fin}}\) logic (hence also in its fragment WMSO+\(\mathsf U\)) to graphs of the Caucal hierarchy we can only obtain graphs on the same level of the hierarchy. Conversely, interpretations described in the more powerful MSO+\(\mathsf U\) logic can give us graphs with undecidable MSO theory, hence outside of the Caucal hierarchy.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Rule-Based Unification in Combined Theories and the Finite Variant Property

next chapter Tight Bounds on the Minimum Size of a Dynamic Monopoly

Carayol and Wöhrle say about an inverse rational mapping, which is a special case of an MSO-interpretation.

Bojańczyk, M.: A bounding quantifier. In: Marcinkowski, J., Tarlecki, A. (eds.) CSL 2004. LNCS, vol. 3210, pp. 41–55. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30124-0_7CrossRef

Bojańczyk, M.: Weak MSO with the unbounding quantifier. Theory Comput. Syst. 48(3), 554–576 (2011). https://doi.org/10.1007/s00224-010-9279-2MathSciNetCrossRefMATH

Bojańczyk, M., Parys, P., Toruńczyk, S.: The MSO+U theory of (N, \(<\)) is undecidable. In: STACS, pp. 21:1–21:8 (2016). https://doi.org/10.4230/LIPIcs.STACS.2016.21

Bojańczyk, M., Toruńczyk, S.: Weak MSO+U over infinite trees. In: STACS, pp. 648–660 (2012). https://doi.org/10.4230/LIPIcs.STACS.2012.648

Cachat, T.: Higher order pushdown automata, the Caucal hierarchy of graphs and parity games. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 556–569. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45061-0_45CrossRefMATH

Carayol, A.: Automates infinis, logiques et langages. Ph.D. thesis. Université de Rennes 1 (2006)

Carayol, A., Wöhrle, S.: The Caucal hierarchy of infinite graphs in terms of logic and higher-order pushdown automata. In: Pandya, P.K., Radhakrishnan, J. (eds.) FSTTCS 2003. LNCS, vol. 2914, pp. 112–123. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-24597-1_10CrossRefMATH

Caucal, D.: On infinite transition graphs having a decidable monadic theory. In: Meyer, F., Monien, B. (eds.) ICALP 1996. LNCS, vol. 1099, pp. 194–205. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61440-0_128CrossRef

Caucal, D.: On infinite terms having a decidable monadic theory. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 165–176. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45687-2_13CrossRef

10.

Colcombet, T.: A combinatorial theorem for trees. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 901–912. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73420-8_77CrossRefMATH

11.

Colcombet, T.: Composition with algebra at the background - on a question by Gurevich and Rabinovich on the monadic theory of linear orderings. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol. 7913, pp. 391–404. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38536-0_34CrossRefMATH

12.

Colcombet, T., Löding, C.: Transforming structures by set interpretations. Log. Methods Comput. Sci. 3(2) (2007). https://doi.org/10.2168/LMCS-3(2:4)2007

13.

Courcelle, B.: Monadic second-order definable graph transductions: a survey. Theoret. Comput. Sci. 126(1), 53–75 (1994). https://doi.org/10.1016/0304-3975(94)90268-2MathSciNetCrossRefMATH

14.

Courcelle, B., Walukiewicz, I.: Monadic second-order logic, graph coverings and unfoldings of transition systems. Ann. Pure Appl. Logic 92(1), 35–62 (1998). https://doi.org/10.1016/S0168-0072(97)00048-1MathSciNetCrossRefMATH

15.

Engelfriet, J.: Iterated stack automata and complexity classes. Inf. Comput. 95(1), 21–75 (1991). https://doi.org/10.1016/0890-5401(91)90015-TMathSciNetCrossRefMATH

16.

Haddad, A.: IO vs OI in higher-order recursion schemes. In: FICS, pp. 23–30 (2012). https://doi.org/10.4204/EPTCS.77.4CrossRef

17.

Hague, M., Murawski, A.S., Ong, C.L., Serre, O.: Collapsible pushdown automata and recursion schemes. In: LICS, pp. 452–461 (2008). https://doi.org/10.1109/LICS.2008.34

18.

Hummel, S., Skrzypczak, M.: The topological complexity of MSO+U and related automata models. Fundam. Inform. 119(1), 87–111 (2012). https://doi.org/10.3233/FI-2012-728MathSciNetCrossRefMATH

19.

Knapik, T., Niwiński, D., Urzyczyn, P.: Higher-order pushdown trees are easy. In: Nielsen, M., Engberg, U. (eds.) FoSSaCS 2002. LNCS, vol. 2303, pp. 205–222. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45931-6_15CrossRef

20.

Ong, C.L.: On model-checking trees generated by higher-order recursion schemes. In: LICS, pp. 81–90 (2006). https://doi.org/10.1109/LICS.2006.38

21.

Parys, P.: Variants of collapsible pushdown systems. In: CSL, pp. 500–515 (2012). https://doi.org/10.4230/LIPIcs.CSL.2012.500

22.

Parys, P.: Recursion schemes, the MSO logic, and the U quantifier (submitted). https://arxiv.org/abs/1810.04763

23.

Parys, P.: A type system describing unboundedness (submitted). https://hal.archives-ouvertes.fr/hal-01850934

24.

Parys, P.: On the significance of the collapse operation. In: LICS, pp. 521–530 (2012). https://doi.org/10.1109/LICS.2012.62

25.

Penelle, V.: Rewriting higher-order stack trees. Theory Comput. Syst. 61(2), 536–580 (2017). https://doi.org/10.1007/s00224-017-9769-6MathSciNetCrossRefMATH

26.

Walukiewicz, I.: Monadic second-order logic on tree-like structures. Theoret. Comput. Sci. 275(1–2), 311–346 (2002). https://doi.org/10.1016/S0304-3975(01)00185-2MathSciNetCrossRefMATH

Title: Extensions of the Caucal Hierarchy?
Author: Paweł Parys
Publisher: Springer International Publishing
Book: Language and Automata Theory and Applications
Print ISBN: 978-3-030-13434-1

Electronic ISBN: 978-3-030-13435-8

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-13435-8_27

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner