Export Citations
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
- research-articleMarch 2015
The Complexity of Decomposing Modal and First-Order Theories
ACM Transactions on Computational Logic (TOCL), Volume 16, Issue 1Article No.: 9, Pages 1–43https://doi.org/10.1145/2699918We study the satisfiability problem of the logic K2 = K × K—the two-dimensional variant of unimodal logic, where models are restricted to asynchronous products of two Kripke frames. Gabbay and Shehtman proved in 1998 that this problem is decidable in a ...
- ArticleJune 2012
The Complexity of Decomposing Modal and First-Order Theories
LICS '12: Proceedings of the 2012 27th Annual IEEE/ACM Symposium on Logic in Computer SciencePages 325–334https://doi.org/10.1109/LICS.2012.43We show that the satisfiability problem for the two-dimensional extension KxK of unimodal K is nonelementary, hereby confirming a conjecture of Marx and Mikulas from 2001. Our lower bound technique allows us to derive further lower bounds for many-...
- articleJanuary 2006
Locality of Queries and Transformations
Electronic Notes in Theoretical Computer Science (ENTCS) (ENTCS), Volume 143Pages 115–127https://doi.org/10.1016/j.entcs.2005.04.041Locality is a standard notion of finite model theory. There are two well known flavors of it, based on Hanf's and Gaifman's theorems. Essentially they say that structures that locally look alike cannot be distinguished by first-order sentences. Very ...