Back to Search
Start Over
On the expressive power of monadic least fixed point logic
- Source :
-
Theoretical Computer Science . Feb2006, Vol. 350 Issue 2/3, p325-344. 20p. - Publication Year :
- 2006
-
Abstract
- Abstract: 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 or, equivalently, settling the question whether would solve open problems in complexity theory: “” would imply that whereas “” would imply that . 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. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 350
- Issue :
- 2/3
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 19469931
- Full Text :
- https://doi.org/10.1016/j.tcs.2005.10.025