English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Post's Correspondence Problem (the PCP) is a classical decision problem in theoretical computer science that asks whether for pairs of free monoid morphismsg  ,  h  :   Σ  ∗   →   Δ  ∗    $g, h\colon \Sigma ^*\rightarrow \Delta ^*$    there exists any non‐trivialx  ∈   Σ  ∗    $x\in \Sigma ^*$    such thatg  (  x  )  =  h  (  x  )   $g(x)=h(x)$   . PCP for a group    Γ  $\Gamma$    takes pairs of group homomorphismsg  ,  h  :  F  (  Σ  )  →  Γ   $g, h\colon F(\Sigma )\rightarrow \Gamma$    instead, and similarly asks whether there exists an    x  $x$    such thatg  (  x  )  =  h  (  x  )   $g(x)=h(x)$    holds for non‐elementary reasons. The restrictions imposed on    x  $x$    in order to get non‐elementary solutions lead to several interpretations of the problem; we mainly consider the natural restriction asking thatx  ∉  ker  (  g  )  ∩  ker  (  h  )   $x \notin \ker (g) \cap \ker (h)$    and prove that the resulting interpretation of the PCP is undecidable for arbitrary hyperbolic    Γ  $\Gamma$   , but decidable when    Γ  $\Gamma$    is virtually nilpotent, en route also studying this problem for finite extensions. We also consider a different interpretation of the PCP due to Myasnikov, Nikolaev and Ushakov, proving decidability for torsion‐free nilpotent groups.

Post's Correspondence Problem for hyperbolic and virtually nilpotent groups