Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRelativization of Gurevichs Conjectures
62
0
0.0
(
0
)
Added by
Anatole Dahan
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 discover interesting conjectures about a given set of functions. QuickSpec works by interleaving term generation with random testing to form candidate conjectures. This is made tractable by starting from small sizes and ensuring that only terms that are irreducible with respect to already discovered conjectures are considered. QuickSpec has been successfully applied to generate lemmas for automated inductive theorem proving as well as to generate specifications of functional programs. We give an overview of typical use-cases of QuickSpec, as well as demonstrating how to easily connect it to a theorem prover of the users choice.
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 {Sigma}11 of (effective) analytic subsets of X{omega} for some finite alphabet X. We investigate here the notion of ambiguity for recursive {omega}-languages with regard to acceptance by Buchi Turing machines. We first present in detail essentials on the literature on {omega}-languages accepted by Turing Machines. Then we give a complete and broad view on the notion of ambiguity and unambiguity of Buchi Turing machines and of the {omega}-languages they accept. To obtain our new results, we make use of results and methods of effective descriptive set theory.
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 interpretations, a termination proof method introduced by the second author, to characterize polygraphic programs that compute in polynomial time. We conclude with a characterization of polynomial time functions and non-deterministic polynomial time functions.
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 the conciliating Wadge hierarchy, defined by J. Duparc, of infinitary context free languages, studied by D. Beauquier. We show also that there exist some omega context free languages which are Sigma^0_omega-complete Borel sets, improving previous results on omega context free languages and the Borel hierarchy.
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-deterministic Petri nets are topologically more complex than those accepted by deterministic Petri nets.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
