The undecidability of joint embedding for 3-dimensional permutation classes

Abstract

As a step towards resolving a question of Ruškuc on the decidability of joint embedding for hereditary classes of permutations, which may be viewed as structures in a language of 2 linear orders, we show the corresponding problem is undecidable for hereditary classes of structures in a language of 3 linear orders.

20 pages. DMTCS version. arXiv admin note: substantial text overlap with arXiv:1903.11932

References in corpus (2)

• Pattern avoidance is not P-recursive
• The undecidability of joint embedding and joint homomorphism for hereditary graph classes