2 papers
cs.FL2026
Weak Bisimulation Finiteness of Pushdown Systems With Deterministic -Transitions Is 2-ExpTime-Complete
Stefan Göller, Paweł Parys
We consider the problem of deciding whether a given pushdown system all of whose -transitions are deterministic is weakly bisimulation finite, that is, whether it is w…
cs.LO2026
A finer reparameterisation theorem for MSO and FO queries on strings
Lê Thà nh Dũng Nguyên, PaweŠParys
We show a theorem on monadic second-order k-ary queries on finite words. It may be illustrated by the following example: if the number of results of a query on binary strings is O(…