BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Philipp Hieronymi (Universität Bonn)
DTSTART:20210928T123000Z
DTEND:20210928T133000Z
DTSTAMP:20260423T040001Z
UID:OWNS/57
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/OWNS/57/">A 
 strong version of Cobham's theorem</a>\nby Philipp Hieronymi (Universität
  Bonn) as part of One World Numeration seminar\n\n\nAbstract\nLet $k\,l>1$
  be two multiplicatively independent integers. A subset $X$ of $\\mathbb{N
 }^n$ is $k$-recognizable if the set of $k$-ary representations of $X$ is r
 ecognized by some finite automaton. Cobham’s famous theorem states that 
 a subset of the natural numbers is both $k$-recognizable and $l$-recogniza
 ble if and only if it is Presburger-definable (or equivalently: semilinear
 ). We show the following strengthening. Let $X$ be $k$-recognizable\, let 
 $Y$ be $l$-recognizable such that both $X$ and $Y$ are not Presburger-defi
 nable. Then the first-order logical theory of $(\\mathbb{N}\,+\,X\,Y)$ is 
 undecidable. This is in contrast to a well-known theorem of Büchi that th
 e first-order logical theory of $(\\mathbb{N}\,+\,X)$ is decidable. Our wo
 rk strengthens and depends on earlier work of Villemaire and Bès.\n\nThe 
 essence of Cobham's theorem is that recognizability depends strongly on th
 e choice of the base $k$. Our results strengthens this: two non-Presburger
  definable sets that are recognizable in multiplicatively independent base
 s\, are not only distinct\, but together computationally intractable over 
 Presburger arithmetic.\n\nThis is joint work with Christian Schulz.\n
LOCATION:https://researchseminars.org/talk/OWNS/57/
END:VEVENT
END:VCALENDAR