The First-Order Theory of Ground Tree Rewrite Graphs
We prove that the complexity of the uniform first-order theory of ground tree rewrite graphs is in ATIME(2^{2^{poly(n)}},O(n)). Providing a matching lower bound, we show that there is some fixed ground tree rewrite graph whose first-order theory is hard for ATIME(2^{2^{poly(n)}},poly(n)) with respec...
| প্রধান লেখক: | , |
|---|---|
| বিন্যাস: | প্রবন্ধ |
| ভাষা: | English |
| প্রকাশিত: |
Logical Methods in Computer Science e.V.
2014-02-01
|
| মালা: | Logical Methods in Computer Science |
| বিষয়গুলি: | |
| অনলাইন ব্যবহার করুন: | https://lmcs.episciences.org/1223/pdf |