ﻻ يوجد ملخص باللغة العربية
Gurevich (1988) conjectured that there is no logic for $textsf{P}$ or for $textsf{NP}cap textsf{coNP}$. For the latter complexity class, he also showed that the existence of a logic would imply that $textsf{NP} cap textsf{coNP}$ has a complete problem under polynomial time reductions. We show that there is an oracle with respect to which $textsf P$ does have a logic and $textsf P etextsf{NP}$. We also show that a logic for $textsf{NP} cap textsf{coNP}$ follows from the existence of a complete problem and a further assumption about canonical labelling. For intersection classes $Sigma^p_n cap Pi^p_n$ higher in the polynomial hierarchy, the existence of a logic is equivalent to the existence of complete problems.
A key component of mathematical reasoning is the ability to formulate interesting conjectures about a problem domain at hand. In this paper, we give a brief overview of a theory exploration system called QuickSpec, which is able to automatically disc
An {omega}-language is a set of infinite words over a finite alphabet X. We consider the class of recursive {omega}-languages, i.e. the class of {omega}-languages accepted by Turing machines with a Buchi acceptance condition, which is also the class
We present polygraphic programs, a subclass of Albert Burronis polygraphs, as a computational model, showing how these objects can be seen as first-order functional programs. We prove that the model is Turing complete. We use polygraphic interpretati
We prove in this paper that the length of the Wadge hierarchy of omega context free languages is greater than the Cantor ordinal epsilon_omega, which is the omega-th fixed point of the ordinal exponentiation of base omega. The same result holds for t
We show that there are $Sigma_3^0$-complete languages of infinite words accepted by non-deterministic Petri nets with Buchi acceptance condition, or equivalently by Buchi blind counter automata. This shows that omega-languages accepted by non-determi