On the Expressive Power of Graph Logic Export

@incollection{citeulike:2443211, abstract = {Graph Logic, a query language being a sublogic of Monadic Second Order Logic is studied in [CGG02]. In the paper [DGG04] the expressiveness power of Graph Logic is examined, and it is shown, for many MSO properties, how to express them in Graph Logic. But despite of the positive examples, it is conjectured there that Graph Logic is strictly less expressive than MSO Logic. Here we give a proof of this conjecture.}, author = {Marcinkowski, Jerzy}, citeulike-article-id = {2443211}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/11874683_32}, doi = {10.1007/11874683_32}, journal = {Computer Science Logic}, keywords = {graphs, logic}, pages = {486--500}, posted-at = {2008-02-28 12:12:31}, priority = {0}, title = {On the Expressive Power of Graph Logic}, url = {http://dx.doi.org/10.1007/11874683_32}, year = {2006} }

TY - CHAP ID - citeulike:2443211 L3 - citeulike-article-id:2443211 N2 - Graph Logic, a query language being a sublogic of Monadic Second Order Logic is studied in [CGG02]. In the paper [DGG04] the expressiveness power of Graph Logic is examined, and it is shown, for many MSO properties, how to express them in Graph Logic. But despite of the positive examples, it is conjectured there that Graph Logic is strictly less expressive than MSO Logic. Here we give a proof of this conjecture. JF - Computer Science Logic EP - 500 TI - On the Expressive Power of Graph Logic SP - 486 KW - graphs KW - logic AU - Marcinkowski, Jerzy PY - 2006/// UR - http://dx.doi.org/10.1007/11874683_32 ER -