Room 327

From Unary to Determinstic Logics for UL

Paritosh Pandya

TIFR

Four widely different temporal logics over finite words are studied: namely TL[F,P], TL[Xa,Ya], Recursive TL[Xphi,Yphi] and interval logic UITL+-. By effective reductions between them, these are shown to be equally expressive. We also give effective reductions between TL[Xa,Ya] and partially ordered 2-way deterministic automata (PO2DFA), thereby establishing that all the four logics exactly characterize the unambiguous star-free regular langauges (UL) of Schutzenberger. Moreover, the reductions from logics to automata are efficient and they allows us to establish the NP-Complete satisfiability of all the four logics.

Clearly an explanation of robustness and efficient decidability of logics for UL is needed. Towards this, we observe that our reductions rely upon on some properties of deterministic temporal logics, namely, unique parsability, ranker directionality and ranker
convexity. These will be explained and motivated.

(This is joint work with Simoni Shah.)