BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Armin Weiß (Universität Stuttgart) DTSTART:20230125T040000Z DTEND:20230125T050000Z DTSTAMP:20260423T021338Z UID:SiN/50 DESCRIPTION:Title: An Automaton Group with PSPACE-Complete Word Problem\nby Armin Weiß (Uni versität Stuttgart) as part of Symmetry in Newcastle\n\n\nAbstract\nFinit e automata pose an interesting alternative way to present groups and \nsem igroups. Some of these automaton groups became famous for their peculiar \ nproperties and have been extensively studied. \n\nOne aspect of this rese arch is the study of algorithmic properties of \nautomaton groups and semi groups. While many natural algorithmic decision \nproblems have been prove n or are generally suspected to be undecidable for \nthese classes\, the w ord problem forms a notable exception. In the group case\, \nit asks wheth er a given word in the generators is equal to the neutral element \nin the group in question and is well-known to be decidable for automaton \ngroup s. In fact\, it was observed in a work by Steinberg published in 2015 that \nit can be solved in nondeterministic linear space using a straight-forw ard \nguess and check algorithm. In the same work\, he conjectured that th ere is an \nautomaton group with a PSPACE-complete word problem.\n\nIn a r ecent paper presented at STACS 2020\, Jan Philipp Wächter and myself coul d\nprove that there indeed is such an automaton group. To achieve this\, w e combined\ntwo ideas. The first one is a construction introduced by D'Ang eli\, Rodaro and\nWächter to show that there is an inverse automaton semi group with a \nPSPACE-complete word problem and the second one is an idea already used \nby Barrington in 1989 to encode NC¹ circuits in the group of even permutation \nover five elements. In the talk\, we will discuss ho w Barrington's idea can be \napplied in the context of automaton groups\, which will allow us to prove that \nthe uniform word problem for automaton groups (were the generating automaton \nand\, thus\, the group is part of the input) is PSPACE- complete. Afterwards\, we \nwill also discuss the i deas underlying the construction to simulate a PSPACE-\nmachine with an in vertible automaton\, which allow for extending the result to \nthe non-uni form case. Finally\, we will briefly look at related problems such \nas th e compressed word problem for automaton groups and the special case of\nau tomaton group of polynomial activity.\n LOCATION:https://researchseminars.org/talk/SiN/50/ END:VEVENT END:VCALENDAR