Around Dot Depth Two.

Autor: Lodaya, Kamal, Pandya, Paritosh K., Shah, Simoni S.
Zdroj: Developments in Language Theory (9783642144547); 2010, p303-315, 13p
Abstrakt: It is known that the languages definable by formulae of the logics ]> are exactly the variety DA*D. Automata for this class are not known, nor is its precise placement within the dot-depth hierarchy of starfree languages. It is easy to argue that ∆2[ < ,S] is included in ∆3[ < ]; in this paper we show that it is incomparable with B(Σ2)[ < ], the boolean combination of Σ2[ < ] formulae. Using ideas from Straubing΄s ˵delay theorem″, we extend our earlier work [LPS08] to propose partially-ordered two-way deterministic finite automata with look-around (po2dla) and a new interval temporal logic called LITL and show that they also characterize the variety DA*D. We give effective reductions from LITL to equivalent po2dla and from po2dla to equivalent FO2[ < ,S]. The po2dla automata admit efficient operations of boolean closure and the language non-emptiness of po2dla is NP-complete. Using this, we show that satisfiability of LITL remains NP-complete assuming a fixed look-around length. (Recall that for LTL[F,X], it is Pspace-hard.) [ABSTRACT FROM AUTHOR]
Databáze: Complementary Index