BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Volker Diekert (Universität Stuttgart)
DTSTART:20221007T050000Z
DTEND:20221007T060000Z
DTSTAMP:20260423T021400Z
UID:SiN/47
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/SiN/47/">Dec
 idability of membership problems for $2\\times 2$ matrices over $\\mathbb{
 Q}$</a>\nby Volker Diekert (Universität Stuttgart) as part of Symmetry in
  Newcastle\n\n\nAbstract\nMy talk is based on a joint work with Igor Potap
 ov and Pavel Semukhin (Liverpool\, UK).\nWe consider membership problems i
 n matrix semigroups. Using symbolic algorithms on words and finite automat
 a\, we prove various new decidability results for $2\\times 2$ matrices ov
 er $\\mathbb{Q}$.\nFor that\, we introduce the concept of flat rational se
 ts: if $M$ is a monoid and $N$ is\na submonoid\, then \\emph{flat rational
  sets of $M$ over $N$} are finite unions of the form $L_0g_1L_1 \\cdots g_
 t L_t$ where all $L_i$'s are rational subsets of $N$ and $g_i\\in M$. We g
 ive quite general sufficient conditions under which flat rational sets for
 m an effective relative Boolean algebra. As a corollary\, we obtain that t
 he emptiness problem for Boolean combinations of flat rational subsets of 
 $\\mathrm{GL}(2\,\\mathbb{Q})$ over $\\mathrm{GL}(2\,\\mathbb{Z})$ is deci
 dable (in singly exponential time). It is possible that such a strong deci
 dability result cannot be pushed any further for groups sitting between\n$
 \\mathrm{GL}(2\,\\mathbb{Z})$ and $\\mathrm{GL}(2\,\\mathbb{Q})$.\n\nWe al
 so show a dichotomy for nontrivial group extension of $\\mathrm{GL}(2\,\\m
 athbb{Z})$ in $\\mathrm{GL}(2\,\\mathbb{Q})$: if $G$ is a f.g.~group such 
 that $\\mathrm{GL}(2\,\\mathbb{Z}) < G \\leq \\mathrm{GL}(2\,\\mathbb{Q})$
 \, then either $G\\cong \\mathrm{GL}(2\,\\mathbb{Z})\\times \\mathbb{Z}^k$
 \, for\nsome $k\\geq 1$\, or $G$ contains an extension of the Baumslag-Sol
 itar group $\\mathop\\mathrm{BS}(1\,q)$\, with $q\\geq\n2$\, of infinite i
 ndex. In the first case of the dichotomy the membership problem for $G$ is
 \ndecidable but the equality problem for rational subsets of $G$ is undeci
 dable. In the second case\,\ndecidability of the membership problem for ra
 tional subsets in $G$ is open.\n\nOur  improves various natural decidabili
 ty results for $2 \\times 2$ matrices with rational entries\, and it also\
 nsupports them with concrete complexity bounds for the first time.\n
LOCATION:https://researchseminars.org/talk/SiN/47/
END:VEVENT
END:VCALENDAR