The First Order Truth behind Undecidability of Regular Path Queries Determinacy
share
In our paper [GMO18] we have solved an old problem stated in [CGLV02] showing that determinacy is undecidable for Regular Path Queries. Here a strong generalisation of this result is shown, and -- we think -- a very unexpected one. We prove that no Regularity is needed: the problem remains undecidable even for finite unions of Path Queries.
READ FULL TEXT