BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Stavros Konstantinidis (Saint Mary's University)
DTSTART:20250618T120000Z
DTEND:20250618T130000Z
DTSTAMP:20260423T021236Z
UID:FLAT/12
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/FLAT/12/">On
  the difference set of two transducers and PRAX algorithms</a>\nby Stavros
  Konstantinidis (Saint Mary's University) as part of One FLAT World Semina
 r\n\n\nAbstract\nThe first part of the talk deals with sets (languages) of
  all inputs $w\\in\\Sigma^*$ on which the output sets of two given transdu
 cers $S$ and $T$ differ\; formally $\\Delta(S\,T) = \\{ w\\in\\Sigma^*  : 
 S(w) \\neq T(w)\\}$\,\nwhere $S$ and $T$ are finite transducers (nondeterm
 inistic\, in general) with the same domain $\\Sigma$.\nHow hard is the pro
 blem $\\{(S\,T\,w) : S(w) ≠ T(w)\\}$ in general --- that is the problem 
 of deciding whether $S(w) ≠ T(w)$ given $S$\, $T$\, and $w$ --- and when
  (at least) one of $S\,T$ is of a restricted type (e.g.\, finite-valued)?\
 n\nDepending on restrictions on $S\,T$\, we have language classes like\n\n
 - $\\Delta(\\text{FINVAL}) = \\{\\Delta(S\,T) : S\,T$ are finite-valued$\\
 }$ and\n\n- $\\Delta(\\text{FUNC}\,\\text{TR}) = \\{\\Delta(S\,T) : S$ is 
 functional and $T$ is any transducer$\\}$.\n\nHow do these language classe
 s compare between themselves and between standard ones like $\\text{CSL}$\
 , $\\text{OCL}$\, $\\text{NCM}$\, $\\text{NP}$?\n\n\nThe second part of th
 e talk deals with the recent method of PRAX algorithms for giving approxim
 ate answers to standard hard problems (in particular $\\text{PSPACE}$-comp
 lete ones like NFA universality) in polynomial time using randomization (s
 ampling). The method is meant to be easily and efficiently implementable. 
 While the method is more meaningful in the context of information theory\,
  we also consider it in a broader theoretical context. For example\, we te
 st that the set of solutions of certain simple Diophantine equations is ap
 proximately empty with high probability.\n
LOCATION:https://researchseminars.org/talk/FLAT/12/
END:VEVENT
END:VCALENDAR