Abstract | ||
---|---|---|
We show that for each property of graphs G in NP there is a sequence Ø1, Ø2, . . . of formulas of the full hybrid logic which are satisfied exactly by the frames in G. Moreover, the size of Øn is bounded by a polynomial. We also show that the same holds for each graph property in the polynomial hierarchy. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1007/978-3-642-20920-8_15 | WoLLIC |
Keywords | Field | DocType |
graph property,np graph property,graphs g,polynomial hierarchy,full hybrid logic,satisfiability | Graph automorphism,Polynomial hierarchy,Discrete mathematics,Combinatorics,Polynomial,Graph property,Tutte polynomial,Algorithm,Matrix polynomial,Chromatic polynomial,Mathematics,NP | Conference |
Volume | ISSN | Citations |
6642 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 6 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Francicleber Martins Ferreira | 1 | 1 | 4.44 |
Cibele Matos Freire | 2 | 1 | 1.36 |
Mario R. F. Benevides | 3 | 143 | 23.75 |
L. Menasché Schechter | 4 | 23 | 4.84 |
Ana Teresa Martins | 5 | 2 | 4.80 |