The Word Problem for Omega Terms over Two Variable Logic.

Room FC1.029, DMat-FCUP
Friday, 20 March, 2015 - 17:00

The word problem for omega terms over a variety (of finite monoids) V is the following decision problem: given two omega terms alpha and beta, does the equation alpha = beta hold for all monoids in V? For the variety DA - which is connected to two variable first order logic FO2[<] - this question can be solved using "rankers". Rankers were introduced by Weis and Immerman based on the turtle programs of Schwentick, Therien and Vollmer and are connected to Lodaya, Pandya and Shah's interval temporal logic. Decidability for DA is a direct consequence of solving the word problem for the varieties in the Trotter Weil Hierarchy, which is an infinite hierarchy of varieties below DA.

This approach yields decision algorithms which need only logarithmic space on a Turing machine and, thus, can be parallelized. This can be seen as an improvement in terms of complexity compared to previous results by Almeida and Zeitoun (for R-trivial semigroups) and Moura (for DA).

Speaker: 

Jan Philipp Wächter (University of Stuttgart, Germany)
Error | CMUP

Error

The website encountered an unexpected error. Please try again later.