Polynomial hierarchy graph properties in hybrid logic
作者：
Highlights：
• Polynomially-bounded growth of sequences of HL formulas expressing PH problems.
• The main result still holds if we discharge global modalities provided that graphs are connected and with loops.
• An alternative proof of the NP-hardness of the fragment of HL without the pattern binder-box-binder.
• Fragments of HL with complete model-checking problems for each degree of the polynomial hierarchy.
摘要
•Polynomially-bounded growth of sequences of HL formulas expressing PH problems.•The main result still holds if we discharge global modalities provided that graphs are connected and with loops.•An alternative proof of the NP-hardness of the fragment of HL without the pattern binder-box-binder.•Fragments of HL with complete model-checking problems for each degree of the polynomial hierarchy.
论文关键词：Hybrid logics,Polynomial hierarchy,Graph properties
论文评审过程：Received 16 January 2012, Revised 10 March 2013, Accepted 3 February 2014, Available online 3 April 2014.
论文官网地址：https://doi.org/10.1016/j.jcss.2014.04.003
