اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدTraversal-invariant characterizations of logarithmic space
86
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
We prove that $omega$-languages of (non-deterministic) Petri nets and $omega$-languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of $omega$-languages of (non-determinist
ic) Petri nets are equal to the Borel and Wadge hierarchies of the class of $omega$-languages of (non-deterministic) Turing machines which also form the class of effective analytic sets. In particular, for each non-null recursive ordinal $alpha < omega_1^{{rm CK}} $ there exist some ${bf Sigma}^0_alpha$-complete and some ${bf Pi}^0_alpha$-complete $omega$-languages of Petri nets, and the supremum of the set of Borel ranks of $omega$-languages of Petri nets is the ordinal $gamma_2^1$, which is strictly greater than the first non-recursive ordinal $omega_1^{{rm CK}}$. We also prove that there are some ${bf Sigma}_1^1$-complete, hence non-Borel, $omega$-languages of Petri nets, and that it is consistent with ZFC that there exist some $omega$-languages of Petri nets which are neither Borel nor ${bf Sigma}_1^1$-complete. This answers the question of the topological complexity of $omega$-languages of (non-deterministic) Petri nets which was left open in [DFR14,FS14].
A semi-computable set S in a computable metric space need not be computable. However, in some cases, if S has certain topological properties, we can conclude that S is computable. It is known that if a semi-computable set S is a compact manifold with
boundary, then the computability of deltaS implies the computability of S. In this paper we examine the case when S is a 1-manifold with boundary, not necessarily compact. We show that a similar result holds in this case under assumption that S has finitely many components.
Omega-powers of finitary languages are omega languages in the form V^omega, where V is a finitary language over a finite alphabet X. Since the set of infinite words over X can be equipped with the usual Cantor topology, the question of the topologica
l complexity of omega-powers naturally arises and has been raised by Niwinski, by Simonnet, and by Staiger. It has been recently proved that for each integer n > 0, there exist some omega-powers of context free languages which are Pi^0_n-complete Borel sets, and that there exists a context free language L such that L^omega is analytic but not Borel. But the question was still open whether there exists a finitary language V such that V^omega is a Borel set of infinite rank. We answer this question in this paper, giving an example of a finitary language whose omega-power is Borel of infinite rank.
We describe a general construction of finiteness spaces which subsumes the interpretations of all positive connectors of linear logic. We then show how to apply this construction to prove the existence of least fixpoints for particular functors in th
e category of finiteness spaces: these include the functors involved in a relational interpretation of lazy recursive algebraic datatypes along the lines of the coherence semantics of system T.
A recent strand of research in structural proof theory aims at exploring the notion of analytic calculi (i.e. those calculi that support general and modular proof-strategies for cut elimination), and at identifying classes of logics that can be captu
red in terms of these calculi. In this context, Wansing introduced the notion of proper display calculi as one possible design framework for proof calculi in which the analiticity desiderata are realized in a particularly transparent way. Recently, the theory of properly displayable logics (i.e. those logics that can be equivalently presented with some proper display calculus) has been developed in connection with generalized Sahlqvist theory (aka unified correspondence). Specifically, properly displayable logics have been syntactically characterized as those axiomatized by analytic inductive axioms, which can be equivalently and algorithmically transformed into analytic structural rules so that the resulting proper display calculi enjoy a set of basic properties: soundness, completeness, conservativity, cut elimination and subformula property. In this context, the proof that the given calculus is complete w.r.t. the original logic is usually carried out syntactically, i.e. by showing that a (cut free) derivation exists of each given axiom of the logic in the basic system to which the analytic structural rules algorithmically generated from the given axiom have been added. However, so far this proof strategy for syntactic completeness has been implemented on a case-by-case base, and not in general. In this paper, we address this gap by proving syntactic completeness for properly displayable logics in any normal (distributive) lattice expansion signature. Specifically, we show that for every analytic inductive axiom a cut free derivation can be effectively generated which has a specific shape, referred to as pre-normal form.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
