کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
439393 | 690545 | 2006 | 20 صفحه PDF | دانلود رایگان |
Monadic least fixed point logic MLFP is a natural logic whose expressiveness lies between that of first-order logic FO and monadic second-order logic MSO. In this paper, we take a closer look at the expressive power of MLFP. Our results are:(1)MLFP can describe graph properties beyond any fixed level of the monadic second-order quantifier alternation hierarchy.(2)On strings with built-in addition, MLFP can describe at least all languages that belong to the linear time complexity class DLIN.(3)Settling the question whether addition-invariant MLFP=?addition-invariant MSO on finite stringsor, equivalently, settling the question whether MLFP=?MSO on finite strings with additionwould solve open problems in complexity theory: “==” would imply that PH=PTIMEPH=PTIME whereas “≠≠” would imply that DLIN≠LINHDLIN≠LINH.Apart from this we give a self-contained proof of the previously known result that MLFP is strictly less expressive than MSO on the class of finite graphs.
Journal: Theoretical Computer Science - Volume 350, Issues 2–3, 7 February 2006, Pages 325–344