il est bien connu que le modal -calculusμμ\mu est l'une des logiques temporelles les plus expressives pour exprimer les propriétés des arbres / graphiques, et que CTL * est strictement moins expressif que le -calculus.μμ\mu Ici, je voudrais demander un exemple de formule -calculus, aussi simple que...
Fermé. Cette question est hors sujet . Il n'accepte pas actuellement les réponses. Vous souhaitez améliorer cette question? Mettez à jour la question afin qu'elle soit sur le sujet pour l'échange théorique de pile informatique. Fermé il y a 7 ans . Comment exprimer " " comme une formule de premier...
J'ai vu certaines personnes utiliser la notation de Krivine pour l'application de fonctions lors de la présentation de la syntaxe du -calculus. Par exemple, le -term (avec la convention normale que l'application de fonction associe à gauche, donc cela signifie en fait ) est écrit (avec une...
Je recherche la complexité de la satisfiabilité d'une formule ou d'une formule où est la formule de la forme: Où est la constante dans et le domaine des variables est également .∃ x 1 , … , x m ∀ y 1 , … , y n , ϕ ϕ ϕ : = ϕ ∧ ϕ | ¬ ϕ | ϕ → ϕ | ψ ψ : = t > t | t∀ y1, … , Yn, ∃ x1, … , Xm,...
Cette question est essentiellement la question que j'ai posée sur Mathoverflow. La logique monadique du second ordre (MSO) est une logique du deuxième ordre avec quantification sur des prédicats unaires. Autrement dit, la quantification sur des ensembles. Il existe plusieurs logiques MSO qui sont...
Le fœtus, si vous n'en avez pas entendu parler, peut être lu ici . Il utilise un système de «matrices d'appel» et de «graphiques d'appel» pour trouver tous les «comportements de récursivité» des appels récursifs dans une fonction. Pour montrer qu'une fonction se termine, cela montre que tous les...
La plupart des systèmes typés dépendants ont des conditions de positivité strictes pour les types inductifs. Quelqu'un connaît-il un exemple où la violation de la condition entraîne une incohérence dans le
Nous savons par le théorème de Church que la détermination de la satisfiabilité du premier ordre est indécidable en général, mais il existe plusieurs techniques que nous pouvons utiliser pour déterminer la satisfiabilité du premier ordre. Le plus évident est de rechercher un modèle fini. Cependant,...
J'ai du mal à comprendre la preuve d'une forte normalisation pour le calcul des constructions. J'essaye de suivre la preuve dans le papier de Herman Geuvers "Une preuve courte et flexible de Normalisation Forte pour le Calcul des Constructions". Je peux bien suivre le raisonnement principal....