Relevant bibliographies by topics / Craig's interpolation

Academic literature on the topic 'Craig's interpolation'

Author: Grafiati
Published: 14 March 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Craig's interpolation.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Craig's interpolation"

1

Beklemishev, L. D. "Provability logic without Craig's interpolation property." Mathematical Notes of the Academy of Sciences of the USSR 45, no. 6 (June 1989): 437–45. http://dx.doi.org/10.1007/bf01158230.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Maffezioli, Paolo, and Eugenio Orlandelli. "Full Cut Elimination and Interpolation for Intuitionistic Logic with Existence Predicate." Bulletin of the Section of Logic 48, no. 2 (June 30, 2019): 137–58. http://dx.doi.org/10.18778/0138-0680.48.2.04.

Full text
Abstract:
In previous work by Baaz and Iemhoff, a Gentzen calculus for intuitionistic logic with existence predicate is presented that satisfies partial cut elimination and Craig's interpolation property; it is also conjectured that interpolation fails for the implication-free fragment. In this paper an equivalent calculus is introduced that satisfies full cut elimination and allows a direct proof of interpolation via Maehara's lemma. In this way, it is possible to obtain much simpler interpolants and to better understand and (partly) overcome the failure of interpolation for the implication-free fragment.
APA, Harvard, Vancouver, ISO, and other styles
3

Sági, Gábor, and Saharon Shelah. "On weak and strong interpolation in algebraic logics." Journal of Symbolic Logic 71, no. 1 (March 2006): 104–18. http://dx.doi.org/10.2178/jsl/1140641164.

Full text
Abstract:
AbstractWe show that there is a restriction, or modification of the finite-variable fragments of First Order Logic in which a weak form of Craig's Interpolation Theorem holds but a strong form of this theorem does not hold. Translating these results into Algebraic Logic we obtain a finitely axiomatizable subvariety of finite dimensional Representable Cylindric Algebras that has the Strong Amalgamation Property but does not have the Superamalgamation Property. This settles a conjecture of Pigozzi [12].
APA, Harvard, Vancouver, ISO, and other styles
4

Mason, Ian. "The metatheory of the classical propositional calculus is not axiomatizable." Journal of Symbolic Logic 50, no. 2 (June 1985): 451–57. http://dx.doi.org/10.2307/2274233.

Full text
Abstract:
In this paper we investigate the first order metatheory of the classical propositional logic. In the first section we prove that the first order metatheory of the classical propositional logic is undecidable. Thus as a mathematical object even the simplest of logics is, from a logical standpoint, quite complex. In fact it is of the same complexity as true first order number theory.This result answers negatively a question of J. F. A. K. van Benthem (see [van Benthem and Doets 1983]) as to whether the interpolation theorem in some sense completes the metatheory of the calculus. Let us begin by motivating the question that we answer. In [van Benthem and Doets 1983] it is claimed that a folklore prejudice has it that interpolation was the final elementary property of first order logic to be discovered. Even though other properties of the propositional calculus have been discovered since Craig's orginal paper [Craig 1957] (see for example [Reznikoff 1965]) there is a lot of evidence for the fundamental nature of the property. In abstract model theory for example one finds that very few logics have the interpolation property. There are two well-known open problems in this area. These are1. Is there a logic satisfying the full compactness theorem as well as the interpolation theorem that is not equivalent to first order logic even for finite models?2. Is there a logic stronger than L(Q), the logic with the quantifierthere exist uncountably many, that is countably compact and has the interpolation property?
APA, Harvard, Vancouver, ISO, and other styles
5

Ono, Hiroakira. "Craig's interpolation theorem for the intuitionistic logic and its extensions—A semantical approach." Studia Logica 45, no. 1 (March 1986): 19–33. http://dx.doi.org/10.1007/bf01881546.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

ALIZADEH, MAJID, FARZANEH DERAKHSHAN, and HIROAKIRA ONO. "UNIFORM INTERPOLATION IN SUBSTRUCTURAL LOGICS." Review of Symbolic Logic 7, no. 3 (May 27, 2014): 455–83. http://dx.doi.org/10.1017/s175502031400015x.

Full text
Abstract:
AbstractUniform interpolation property of a given logic is a stronger form of Craig’s interpolation property where both pre-interpolant and post-interpolant always exist uniformly for any provable implication in the logic. It is known that there exist logics, e.g., modal propositional logic S4, which have Craig’s interpolation property but do not have uniform interpolation property. The situation is even worse for predicate logics, as classical predicate logic does not have uniform interpolation property as pointed out by L. Henkin.In this paper, uniform interpolation property of basic substructural logics is studied by applying the proof-theoretic method introduced by A. Pitts (Pitts, 1992). It is shown that uniform interpolation property holds even for their predicate extensions, as long as they can be formalized by sequent calculi without contraction rules. For instance, uniform interpolation property of full Lambek predicate calculus, i.e., the substructural logic without any structural rule, and of both linear and affine predicate logics without exponentials are proved.
APA, Harvard, Vancouver, ISO, and other styles
7

Rodenburg, P. H. "Interpolation in Conditional Equational Logic1." Fundamenta Informaticae 15, no. 1 (June 1, 1991): 80–85. http://dx.doi.org/10.3233/fi-1991-15106.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Molnár, Zalán, and Öztürk Övge. "Notes on localizing Craig’s interpolation theorem." Elpis. Filozófiatudományi Folyóirat 15, no. 1-2 (2022): 103–16. http://dx.doi.org/10.54310/elpis.2022.1.8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Kowalski, Tomasz. "PDL has interpolation." Journal of Symbolic Logic 67, no. 3 (September 2002): 933–46. http://dx.doi.org/10.2178/jsl/1190150141.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Feferman, Solomon. "Harmonious logic: Craig’s interpolation theorem and its descendants." Synthese 164, no. 3 (July 1, 2008): 341–57. http://dx.doi.org/10.1007/s11229-008-9354-2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Craig's interpolation"

1

Weissenbacher, Georg. "Program analysis with interpolants." Thesis, University of Oxford, 2010. http://ora.ox.ac.uk/objects/uuid:6987de8b-92c2-4309-b762-f0b0b9a165e6.

Full text
Abstract:
This dissertation discusses novel techniques for interpolation-based software model checking, an approximate method which uses Craig interpolation to compute invariants of programs. Our work addresses two aspects of program analyses based on model checking: verification (the construction of correctness proofs for programs) and falsification (the detection of counterexamples that violate the specification). In Hoare's calculus, a proof of correctness comprises assertions which establish that a program adheres to its specification. The principal challenge is to derive appropriate assertions and loop invariants. Contemporary software verification tools use Craig interpolation (as opposed to traditional predicate transformers such as the weakest precondition) to derive approximate assertions. The performance of the model checker is contingent on the Craig interpolants computed. We present novel interpolation techniques which provide the following advantages over existing methods. Firstly, the resulting interpolants are sound with respect to the bit-level semantics of programs, which is an improvement over interpolation systems that use linear arithmetic over the reals to approximate bit-vector arithmetic and/or do not support bit-level operations. Secondly, our interpolation systems afford us a choice of interpolants and enable us to fine-tune their logical strength and structure. In contrast, existing procedures are limited to a single ad-hoc choice of an interpolant. Interpolation-based verification tools are typically forced to refine an initial approximation repeatedly in order to achieve the accuracy required to establish or refute the correctness of a program. The detection of a counterexample containing a repetitive construct may necessitate one refinement step (involving the computation of additional interpolants) for each iteration of the loop. We present a heuristic that aims to avoid the repeated and computationally expensive construction of interpolants, thus enabling the detection of deeply buried defects such as buffer overflows. Finally, we present an implementation of our techniques and evaluate them on a set of standardised device driver and buffer overflow benchmarks.
APA, Harvard, Vancouver, ISO, and other styles
2

Barbier, Fabrice. "Résultats de théorie abstraite des modèles dans le cadre des institutions : vers la combinaison de logiques." Phd thesis, Université d'Evry-Val d'Essonne, 2005. http://tel.archives-ouvertes.fr/tel-00087587.

Full text
Abstract:
De nombreux travaux ont montré l'importance de l'interpolation de Craig pour la structuration et la modularité des spécifications de type axiomatique. En vue d'en donner des conditions suffisantes dans un cadre théorique adapté à l'informatique, nous nous sommes intéressé à une propriété équivalente à l'interpolation de Craig dans le cadre de la théorie standard des modèles : la consistance de Robinson. L'étude de cette dernière propriété nous a amené à généraliser dans une spécialisation des institutions les notions classiques de diagrammes complets et de morphismes élémentaires. Ceci nous a alors permis de généraliser quelques résultats classiques de théorie des modèles tels que les théorèmes de Löwenheim-Skolem ou l'union de chaînes de Tarski. En fin, les constructeurs de formules étant explicites dans notre cadre théorique, nous nous sommes naturellemant intéressés à la combinaison de logiques et à la préservation de l'interpolation de Craig et de la consistance de Robinson.
APA, Harvard, Vancouver, ISO, and other styles
3

Xiong, Li-Yu, and 熊立宇. "Craig Interpolation Theorem." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/87462903790124238437.

Full text
Abstract:
碩士
國立中正大學
哲學所
97
In this paper we will survey two different proofs of the Craig interpolation theorem. In the first order logic, the Craig interpolation theorem is a useful result about the connection between two theories. Roughly speaking, for any two sentences φ and ψ with φ│=ψ, there exists a sentence θ, called an interpolant, such that φ│=θ and θ│=ψ, where φ and ψ can belong to two different languages, and the interpolant θ only uses the common part of two languages of φ and ψ. That is, the logical entailment φ│=ψ can be achieved through some interpolant θ (from their common part) by φ│=θ and θ│=ψ. The Craig interpolation theorem was first proved by William Craig in 1957. In chapter I, we introduce basic knowledge of model theory. In chapter II, we follow the approach of Chang-Keisler, which resembles the proof of the completeness theorem to prove the Craig interpolation theorem by the inseparable method. In chapter III, we take a game-theoretic approach to prove the Craig interpolation theorem by the back-and-forth argument (see Doets).
APA, Harvard, Vancouver, ISO, and other styles
4

Lin, Hsuan-Po, and 林炫伯. "Large Scale Ashenhurst Decomposition via SAT Solving and Craig Interpolation." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/91435812875963719114.

Full text
Abstract:
碩士
國立臺灣大學
電子工程學研究所
97
Functional decomposition aims at decomposing a Boolean function into a set of smaller sub-functions. In this thesis, we focus on Ashenhurst decomposition, which has practical applications due to its simplicity. We formulate the decomposition problem as SAT solving, and further apply Craig interpolation and functional dependency computation to derive composite functions. In our pure SAT-based solution, variable partitioning can be automated and integrated into the decomposition procedure. Also we can easily extend our method to non-disjoint and multiple-output decompositions which are hard to handle using BDD-based algorithms. Experimental results show the scalability of our proposed method, which can effectively decompose functions with up to 300 input variables.
APA, Harvard, Vancouver, ISO, and other styles
5

Lin, Ting-Hao, and 林庭豪. "Using SAT-based Craig Interpolation to Enlarge Clock Gating Functions." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/29140781507819471872.

Full text
Abstract:
碩士
國立臺灣大學
電機工程學研究所
99
Dynamic power saving is gaining its dominance in modern low power designs, while clock gating, which blocks unnecessary clock switching activities, is one of the most efficient approaches to reduce the dynamic power. In this thesis, we exploit the interpolation technique in a SAT-based clock gating algorithm in order to grant a greater flexibility in enlarging the gating capabilities over the original gating candidates. We also developed several techniques to improve the runtime and memory usage of the clock gating algorithm, including a gating capability filter to reduce the number of formal SAT proofs, a dynamic backtracking limit controller to shorten the SAT runs, and a shrinking method to ease the final gate count overhead. The experimental results show that our proposed algorithm can gate up to 2X clock switches with less than 5% area overhead when compared to the state-of-the-art SAT-based clock gating methodology.
APA, Harvard, Vancouver, ISO, and other styles
6

Han, Cheng-Shen, and 韓承駪. "A Study of Gaussian Elimination on Boolean Satisfiability and Craig Interpolation." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/86700561504561244362.

Full text
Abstract:
碩士
國立臺灣大學
電子工程學研究所
100
The Boolean satisfiability problem (SAT) is one of the central problems in computer science of both theoretical and practical interests. SAT is the first discovered NP-complete problem, and many real-world computation problems, such as hardware and software verification, electronic design automation (EDA), artificial intelligence (AI), circuit design, automatic theorem proving, etc., can be naturally encoded as SAT instances and solved efficiently. Although impressive advancements of SAT solving have been achieved, recent research reveals modern solvers'' inability to handle formulae in the abundance of parity xor constraints. Although xor-handling in SAT solving has attracted much attention, challenges remain to completely deduce xor-inferred implications and conflicts, to effectively reduce expensive overhead, and to directly generate compact interpolants. This thesis presents a new SAT solver, SimpSat, which integrates SAT solving tightly with Gaussian elimination in the style of Dantzig''s simplex method. It yields a powerful tool overcoming these challenges. Experiments show promising performance improvements and efficient derivation of compact interpolants, which are otherwise unobtainable.
APA, Harvard, Vancouver, ISO, and other styles
7

Rocchetto, Marco. "Methods and tools for design time and runtime formal analysis of security protocols and web applications." Doctoral thesis, 2015. http://hdl.handle.net/11562/913185.

Full text
Abstract:
La crescente complessità delle applicazioni web insieme ai protocolli sottostanti di sicurezza ha fatto rapidamente crescere la necessità di un'analisi automatica tramite metodologie e applicativi. In questa tesi, tratto questo problema proponendo due nuovi approcci formali per la verifica dei protocolli di sicurezza e di applicazioni web. Il primo è un metodo per la verifica di protocolli di sicurezza a tempo di design basato sull'interpolazione. Questo metodo comincia da una specifica di un protocollo e combina interpolazione di Craig, esecuzione simbolica e il modello standard di intruder Dolev-Yao per cercare possibili attacchi al protocollo. Gli interpolanti vengono generati come risposta ad un insuccesso durante la ricerca per poter eliminare tracce inutili e velocizzare l'esplorazione. Il secondo è un metodo per l'analisi di sicurezza a runtime che cerca errori di implementazione e logici su un sistema (web) concreto. In particolare, mi sono concentrato su come usare il modello di intruder Dolev-Yao per cercare attacchi Cross-Site Request Forgery (CSRF). CSRF compare nella lista dei 10 attacchi più critici per la sicurezza web di Open Web Application Security Project (OWASP).
The increasing complexity of web applications together with their underling security protocols has rapidly increased the need of automatic security analysis methods and tools. In this thesis, I address this problem by proposing two new formal approaches for the security verification of security protocols and web applications. The first is a design time interpolation-based method for security protocol verification. This method starts from a protocol specification and combines Craig interpolation, symbolic execution and the standard Dolev-Yao intruder model to search for possible attacks on the protocol. Interpolants are generated as a response to search failure in order to prune possible useless traces and speed up the exploration. The second is a runtime (model-based) security analysis technique that searches for logic and implementation flaws on concrete (web-based) systems. In particular, I focused on how to use the Dolev-Yao intruder model to search for Cross-Site Request Forgery (CSRF) attacks. CSRF is listed in the top ten list of the Open Web Application Security Project (OWASP) as one of the most critical threats to web security.
APA, Harvard, Vancouver, ISO, and other styles
8

Jančík, Pavel. "Reprezentace stavů programu." Doctoral thesis, 2017. http://www.nusl.cz/ntk/nusl-369534.

Full text
Abstract:
Při verifikaci programů se snažíme rozhodnout, zda program obsahuje či neobsahuje chyby. Základním předpokladem všech verifikačních postupů je efektivní reprezentace a manipulace se stavy programů. V této práci představujeme techniky pro nalezení nepodstatných informací ve stavech programů a pro jejich odstranění. Tato práce obsahuje redukce vhodné pro explicitní i symbolickou reprezentaci stavů. Naše postupy vhodné pro explicitní reprezentaci byly speciálně navrženy pro vícevláknové programy. Naše analýzy dokáží nalézt takové hodnoty v dynamicky alokovaných objektech, tedy na haldě, které program již nebude v následujících krocích číst. Logické formule v predikátové nebo výrokové logice jsou převažující symbolickou reprezentací množin stavů programu. Craigovy interpolanty jsou jedním z obvyklých postupů pro získání formulí s požadovanými vlastnostmi. V této práci představujeme nový způsob jejich výpočtu, který používá přiřazení proměnných pro zmenšení jejich velikosti. Pomocí přiřazení proměnných můžeme zablokovat ty cesty v programu, které nechceme, aby interpolant bral v potaz a tím zmenšit jejich velikost.
APA, Harvard, Vancouver, ISO, and other styles
9

Blicha, Martin. "Metody pro redukci velikosti interpolantů při použití částečného přiřazení." Master's thesis, 2016. http://www.nusl.cz/ntk/nusl-352598.

Full text
Abstract:
Abstract. Since the introduction of interpolants to the field of symbolic model checking, interpolation-based methods have been successfully used in both hardware and software model checking. Recently, variable assignments have been introduced to the computation of interpolants. In the context of abstract reachability graphs, variable assignment can be used not only to prevent out-of-scope variables from appearing in interpolants, but also to reduce the size of the interpolant significantly. We further extend the framework for computing interpolants under variable assignment, prove the correctness of the system and show that it has potential to further decrease the size of the computed interpolants. At the end we analyze under which conditions the computed interpolants will still have the path interpolation property, a desired property in many interpolation-based techniques. 1
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Craig's interpolation"

1

Huang, Guoxiang. "Constructing Craig interpolation formulas." In Lecture Notes in Computer Science, 181–90. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. http://dx.doi.org/10.1007/bfb0030832.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

McMillan, Ken L. "Craig Interpolation and Reachability Analysis." In Static Analysis, 336. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/3-540-44898-5_18.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Brotherston, James, and Rajeev Goré. "Craig Interpolation in Displayable Logics." In Lecture Notes in Computer Science, 88–103. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-22119-4_9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Gheerbrant, Amélie, and Balder ten Cate. "Craig Interpolation for Linear Temporal Languages." In Computer Science Logic, 287–301. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-04027-6_22.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Jaakkola, Reijo. "Uniform Guarded Fragments." In Lecture Notes in Computer Science, 409–27. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-030-99253-8_21.

Full text
Abstract:
AbstractIn this paper we prove that the uniform one-dimensional guarded fragment, which is a natural polyadic generalization of guarded two-variable logic, has the Craig interpolation property. We will also prove that the satisfiability problem of uniform guarded fragment is NExpTime-complete.
APA, Harvard, Vancouver, ISO, and other styles
6

Ghilardi, Silvio, Alessandro Gianola, and Deepak Kapur. "Interpolation and Amalgamation for Arrays with MaxDiff." In Lecture Notes in Computer Science, 268–88. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-71995-1_14.

Full text
Abstract:
AbstractIn this paper, the theory of McCarthy’s extensional arrays enriched with a maxdiff operation (this operation returns the biggest index where two given arrays differ) is proposed. It is known from the literature that a diff operation is required for the theory of arrays in order to enjoy the Craig interpolation property at the quantifier-free level. However, the diff operation introduced in the literature is merely instrumental to this purpose and has only a purely formal meaning (it is obtained from the Skolemization of the extensionality axiom). Our maxdiff operation significantly increases the level of expressivity; however, obtaining interpolation results for the resulting theory becomes a surprisingly hard task. We obtain such results via a thorough semantic analysis of the models of the theory and of their amalgamation properties. The results are modular with respect to the index theory and it is shown how to convert them into concrete interpolation algorithms via a hierarchical approach.
APA, Harvard, Vancouver, ISO, and other styles
7

Carbone, A. "The Craig Interpolation Theorem for Schematic Systems." In Collegium Logicum, 87–100. Vienna: Springer Vienna, 1996. http://dx.doi.org/10.1007/978-3-7091-9461-4_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

McMillan, Kenneth. "Applications of Craig Interpolation to Model Checking." In Computer Science Logic, 22–23. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-30124-0_3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

McMillan, Kenneth. "Applications of Craig Interpolation to Model Checking." In Applications and Theory of Petri Nets 2005, 15–16. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11494744_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Teige, Tino, and Martin Fränzle. "Generalized Craig Interpolation for Stochastic Boolean Satisfiability Problems." In Tools and Algorithms for the Construction and Analysis of Systems, 158–72. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-19835-9_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Craig's interpolation"

1

Lin, Ting-Hao, and Chung-Yang (Ric) Huang. "Using SAT-based Craig interpolation to enlarge clock gating functions." In the 48th Design Automation Conference. New York, New York, USA: ACM Press, 2011. http://dx.doi.org/10.1145/2024724.2024867.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Sauer, Matthias, Stefan Kupferschmid, Alexander Czutro, Ilia Polian, Sudhakar Reddy, and Bernd Becker. "Functional test of small-delay faults using SAT and Craig interpolation." In 2012 IEEE International Test Conference (ITC). IEEE, 2012. http://dx.doi.org/10.1109/test.2012.6401550.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Sauer, Matthias, Stefan Kupferschmid, Alexander Czutro, Sudhakar Reddy, and Bernd Becker. "Analysis of Reachable Sensitisable Paths in Sequential Circuits with SAT and Craig Interpolation." In 2012 25th International Conference on VLSI Design. IEEE, 2012. http://dx.doi.org/10.1109/vlsid.2012.101.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Scholl, Christoph, Stefan Disch, Florian Pigorsch, and Stefan Kupferschmid. "Using an SMT solver and Craig interpolation to detect and remove redundant linear constraints in representations of non-convex polyhedra." In the Joint Workshops of the 6th International Workshop on Satisfiability Modulo Theories and 1st International Workshop. New York, New York, USA: ACM Press, 2008. http://dx.doi.org/10.1145/1512464.1512469.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Fortin, Marie, Boris Konev, and Frank Wolter. "Interpolants and Explicit Definitions in Extensions of the Description Logic EL." In 19th International Conference on Principles of Knowledge Representation and Reasoning {KR-2022}. California: International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/kr.2022/16.

Full text
Abstract:
We show that the vast majority of extensions of the description logic EL do not enjoy the Craig interpolation nor the projective Beth definability property. This is the case, for example, for EL with nominals, EL with the universal role, EL with role hierarchies and transitive roles, and for ELI. It follows in particular that the existence of an explicit definition of a concept or individual name cannot be reduced to subsumption checking via implicit definability. We show that nevertheless the existence of interpolants and explicit definitions can be decided in polynomial time for standard tractable extensions of EL (such as EL++) and in ExpTime for ELI and various extensions. It follows that these existence problems are not harder than subsumption which is in sharp contrast to the situation for expressive DLs. We also obtain tight bounds for the size of interpolants and explicit definitions and the complexity of computing them: single exponential for tractable standard extensions of EL and double exponential for ELI and extensions. We close with a discussion of Horn-DLs such as Horn-ALCI.
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Craig's interpolation"

1

Jain, Himanshu, Edmund M. Clarke, and Orna Grumberg. Efficient Craig Interpolation for Linear Diophantine (Dis)Equations and Linear Modular Equations. Fort Belvoir, VA: Defense Technical Information Center, February 2008. http://dx.doi.org/10.21236/ada476801.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Craig's interpolation' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography