BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Nelma Moreira (Universidade do Porto & CMUP) DTSTART:20250530T130000Z DTEND:20250530T140000Z DTSTAMP:20260423T021240Z UID:FLAT/11 DESCRIPTION:Title: Sy nchronised shuffles and team automata\nby Nelma Moreira (Universidade do Porto & CMUP) as part of One FLAT World Seminar\n\n\nAbstract\nThe shuf fle operation has been extensively studied in formal language theory.\nReg ular expressions with shuffle provide succinct representations for modelli ng concurrent systems. However\, even for regular languages\, shuffle is h ard: membership is NP-complete\, inequivalence is EXP-complete\, the conve rsion to NFAs is in the worst-case exponential\, and the conversion to DFA s is double exponential. There are also numerous open problems\, such as e stablishing tight bounds for state complexity even for the shuffle of two words.\nStandard shuffle models the pure interleaving of two concurrent sy stems. To model synchronisation\, and inspired in the Team Automata framew ork\, synchronised shuffle operators allow us to specify symbols on which the operands must or can synchronise instead of interleave. Intersection i s thus an extreme case of synchronisation.\nWe consider conversions of reg ular expressions with several generalised synchronised shuffle operators t o NFAs\, as well as studying some asymptotic average complexities.\n LOCATION:https://researchseminars.org/talk/FLAT/11/ END:VEVENT END:VCALENDAR