Report
Traversal-invariant characterizations of logarithmic space
| العنوان: | Traversal-invariant characterizations of logarithmic space |
|---|---|
| المؤلفون: | Bhaskar, Siddharth, Lindell, Steven, Weinstein, Scott |
| سنة النشر: | 2020 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Logic in Computer Science, Mathematics - Logic, F.4.1 |
| الوصف: | We give a novel descriptive-complexity theoretic characterization of L and NL computable queries over finite structures using traversal invariance. We summarize this as (N)L = FO + (breadth-first) traversal-invariance. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2006.07067 |
| رقم الانضمام: | edsarx.2006.07067 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |