Samuel Braunfeld - The undecidability of joint embedding for 3-dimensional permutation classes

dmtcs:6165 - Discrete Mathematics & Theoretical Computer Science, September 14, 2021, vol. 22 no. 2, Permutation Patterns 2019 - https://doi.org/10.46298/dmtcs.6165
The undecidability of joint embedding for 3-dimensional permutation classesArticle

Authors: Samuel Braunfeld ORCID

    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.

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

    https://doi.org/10.46298/dmtcs.6165
    Source: arXiv.org:2002.11494
    Volume: vol. 22 no. 2, Permutation Patterns 2019
    Section: Special issues
    Published on: September 14, 2021
    Accepted on: August 10, 2021
    Submitted on: February 28, 2020
    Keywords: Mathematics - Logic, Mathematics - Combinatorics
    Licence: Attribution 4.0 International (CC BY 4.0)

    Share and export

    Consultation statistics

    This page has been seen 712 times.
    This article's PDF has been downloaded 549 times.