The first part of the talk deals with sets (languages) of all inputs \(w\in\Sigma^*\) on which the output sets of two given transducers \(S\) and \(T\) differ; formally \(\Delta(S,T) = \{ w\in\Sigma^* : S(w) \neq T(w)\}\), where \(S\) and \(T\) are finite transducers (nondeterministic, in general) with the same domain \(\Sigma\). How hard is the problem \(\{(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)?
Depending on restrictions on \(S,T\), we have language classes like
- \(\Delta(\text{FINVAL}) = \{\Delta(S,T) : S,T\text{ are finite-valued}\}\) and
- \(\Delta(\text{FUNC},\text{TR}) = \{\Delta(S,T) : S \text{ is functional and }T\text{ is any transducer}\}\).
How do these language classes compare between themselves and between standard ones like \(\text{CSL}\), \(\text{OCL}\), \(\text{NCM}\), \(\text{NP}\)?
The second part of the talk deals with the recent method of PRAX algorithms for giving approximate answers to standard hard problems (in particular \(\text{PSPACE}\)-complete ones like NFA universality) in polynomial time using randomization (sampling). 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 test that the set of solutions of certain simple Diophantine equations is approximately empty with high probability.