BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Szilárd Zsolt Fazekas (Akita University) DTSTART:20240410T080000Z DTEND:20240410T090000Z DTSTAMP:20260423T035740Z UID:FLAT/3 DESCRIPTION:Title: Non -regular complexity\nby Szilárd Zsolt Fazekas (Akita University) as p art of One FLAT World Seminar\n\n\nAbstract\nGiven a computational model A \, we will call another model B an extension of A if computation steps pos sible in a system (machine\, grammar\, etc.) of type A are also possible i n systems of type B and the latter allow some operations that are not poss ible in the former. Such a relationship between models is exhibited by con text-free grammars as extensions of regular grammars\, or one-way jumping automata and automata with translucent letters as extensions of finite aut omata. The operations available in the extensions but not in the original model can be viewed as a computational resource and hence can be analyzed quantitatively\, similarly to computational complexity theory. Recent year s saw both the continuation of lines of inquiry from decades ago\, countin g the non-regular rules used in context-free derivations (Bordihn and Mitr ana\, '20)\, and the start of new ones\, counting the number of jumps/swee ps used during computations with the aforementioned extended automata mode ls (Fazekas and Mercaş\, '22-23\, Mitrana et al.\, '24). As the base mode l in all three cases generates/accepts the class of regular languages\, th e complexity notions introduced can be viewed as a measure of how non-regu lar a machine\, grammar or language is. In this talk I give an overview of the research concerning the hierarchies of language classes defined throu gh these non-regular complexity measures\, and propose some questions for further investigation.\n LOCATION:https://researchseminars.org/talk/FLAT/3/ END:VEVENT END:VCALENDAR