Showing cs.LOShow all
2 papers · 1 filter
cs.LO2023
PDL on Steroids: on Expressive Extensions of PDL with Intersection and Converse
Diego Figueira, Santiago Figueira, Edwin Pin
We introduce CPDL+, a family of expressive logics rooted in Propositional Dynamic Logic (PDL). In terms of expressive power, CPDL+ strictly contains PDL extended with intersection…
cs.LO2017
A syntactic tool for proving hardness in the Second Level of the Polynomial-Time Hierarchy
Edwin Pin, Nerio Borges
In the nineties Immerman and Medina initiated the search for syn- tactic tools to prove NP-completeness. In their work, amongst several results, they conjecture that the NP-complet…