Relevant bibliographies by topics / Tractable reasoning

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers

Academic literature on the topic 'Tractable reasoning'

Author: Grafiati
Published: 4 June 2021
Last updated: 5 February 2022

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

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Tractable reasoning.'

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 "Tractable reasoning"

1

Schaerf, Marco, and Marco Cadoli. "Tractable reasoning via approximation." Artificial Intelligence 74, no. 2 (April 1995): 249–310. http://dx.doi.org/10.1016/0004-3702(94)00009-p.

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

Bodirsky, M., and M. Hils. "Tractable Set Constraints." Journal of Artificial Intelligence Research 45 (December 31, 2012): 731–59. http://dx.doi.org/10.1613/jair.3747.

Full text
Abstract:
Many fundamental problems in artificial intelligence, knowledge representation, and verification involve reasoning about sets and relations between sets and can be modeled as set constraint satisfaction problems (set CSPs). Such problems are frequently intractable, but there are several important set CSPs that are known to be polynomial-time tractable. We introduce a large class of set CSPs that can be solved in quadratic time. Our class, which we call EI, contains all previously known tractable set CSPs, but also some new ones that are of crucial importance for example in description logics. The class of EI set constraints has an elegant universal-algebraic characterization, which we use to show that every set constraint language that properly contains all EI set constraints already has a finite sublanguage with an NP-hard constraint satisfaction problem.
APA, Harvard, Vancouver, ISO, and other styles
3

Fang, Liangda, Kewen Wang, Zhe Wang, and Ximing Wen. "Disjunctive Normal Form for Multi-Agent Modal Logics Based on Logical Separability." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 2817–26. http://dx.doi.org/10.1609/aaai.v33i01.33012817.

Full text
Abstract:
Modal logics are primary formalisms for multi-agent systems but major reasoning tasks in such logics are intractable, which impedes applications of multi-agent modal logics such as automatic planning. One technique of tackling the intractability is to identify a fragment called a normal form of multiagent logics such that it is expressive but tractable for reasoning tasks such as entailment checking, bounded conjunction transformation and forgetting. For instance, DNF of propositional logic is tractable for these reasoning tasks. In this paper, we first introduce a notion of logical separability and then define a novel disjunctive normal form SDNF for the multiagent logic Kn, which overcomes some shortcomings of existing approaches. In particular, we show that every modal formula in Kn can be equivalently casted as a formula in SDNF, major reasoning tasks tractable in propositional DNF are also tractable in SDNF, and moreover, formulas in SDNF enjoy the property of logical separability. To demonstrate the usefulness of our approach, we apply SDNF in multi-agent epistemic planning. Finally, we extend these results to three more complex multi-agent logics Dn, K45n and KD45n.
APA, Harvard, Vancouver, ISO, and other styles
4

Pan, Jeff, Edward Thomas, Yuan Ren, and Stuart Taylor. "Exploiting Tractable Fuzzy and Crisp Reasoning in Ontology Applications." IEEE Computational Intelligence Magazine 7, no. 2 (May 2012): 45–53. http://dx.doi.org/10.1109/mci.2012.2188588.

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

Mailis, Theofilos, Giorgos Stoilos, Nikolaos Simou, Giorgos Stamou, and Stefanos Kollias. "Tractable reasoning with vague knowledge using fuzzy $\mathcal{EL}^{++}$." Journal of Intelligent Information Systems 39, no. 2 (March 24, 2012): 399–440. http://dx.doi.org/10.1007/s10844-012-0195-6.

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

Cristani, M. "The Complexity of Reasoning about Spatial Congruence." Journal of Artificial Intelligence Research 11 (November 20, 1999): 361–90. http://dx.doi.org/10.1613/jair.641.

Full text
Abstract:
In the recent literature of Artificial Intelligence, an intensive research effort has been spent, for various algebras of qualitative relations used in the representation of temporal and spatial knowledge, on the problem of classifying the computational complexity of reasoning problems for subsets of algebras. The main purpose of these researches is to describe a restricted set of maximal tractable subalgebras, ideally in an exhaustive fashion with respect to the hosting algebras. In this paper we introduce a novel algebra for reasoning about Spatial Congruence, show that the satisfiability problem in the spatial algebra MC-4 is NP-complete, and present a complete classification of tractability in the algebra, based on the individuation of three maximal tractable subclasses, one containing the basic relations. The three algebras are formed by 14, 10 and 9 relations out of 16 which form the full algebra.
APA, Harvard, Vancouver, ISO, and other styles
7

McIntyre, Stephanie, Alexander Borgida, David Toman, and Grant Weddell. "On Limited Conjunctions and Partial Features in Parameter-Tractable Feature Logics." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 2995–3002. http://dx.doi.org/10.1609/aaai.v33i01.33012995.

Full text
Abstract:
Standard reasoning problems are complete for EXPTIME in common feature-based description logics—ones in which all roles are restricted to being functions. We show how to control conjunctions on left-hand-sides of subsumptions and use this restriction to develop a parameter-tractable algorithm for reasoning about knowledge base consistency. We then show how the resulting logic can simulate partial features, and present algorithms for efficient query answering in that setting.
APA, Harvard, Vancouver, ISO, and other styles
8

Eiter, Thomas, and Thomas Lukasiewicz. "Default reasoning from conditional knowledge bases: Complexity and tractable cases." Artificial Intelligence 124, no. 2 (December 2000): 169–241. http://dx.doi.org/10.1016/s0004-3702(00)00073-4.

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

Jones, C. B. "The early search for tractable ways of reasoning about programs." IEEE Annals of the History of Computing 25, no. 2 (April 2003): 26–49. http://dx.doi.org/10.1109/mahc.2003.1203057.

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

Borges Garcia, Berilhes. "New tractable classes for default reasoning from conditional knowledge bases." Annals of Mathematics and Artificial Intelligence 45, no. 3-4 (November 16, 2005): 275–91. http://dx.doi.org/10.1007/s10472-005-9000-3.

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

Dissertations / Theses on the topic "Tractable reasoning"

1

Ren, Yuan. "Tractable reasoning with quality guarantee for expressive description logics." Thesis, University of Aberdeen, 2014. http://digitool.abdn.ac.uk:80/webclient/DeliveryManager?pid=217884.

Full text
Abstract:
DL-based ontologies have been widely used as knowledge infrastructures in knowledge management systems and on the Semantic Web. The development of efficient, sound and complete reasoning technologies has been a central topic in DL research. Recently, the paradigm shift from professional to novice users, and from standalone and static to inter-linked and dynamic applications raises new challenges: Can users build and evolve ontologies, both static and dynamic, with features provided by expressive DLs, while still enjoying e cient reasoning as in tractable DLs, without worrying too much about the quality (soundness and completeness) of results? To answer these challenges, this thesis investigates the problem of tractable and quality-guaranteed reasoning for ontologies in expressive DLs. The thesis develops syntactic approximation, a consequence-based reasoning procedure with worst-case PTime complexity, theoretically sound and empirically high-recall results, for ontologies constructed in DLs more expressive than any tractable DL. The thesis shows that a set of semantic completeness-guarantee conditions can be identifed to efficiently check if such a procedure is complete. Many ontologies tested in the thesis, including difficult ones for an off-the-shelf reasoner, satisfy such conditions. Furthermore, the thesis presents a stream reasoning mechanism to update reasoning results on dynamic ontologies without complete re-computation. Such a mechanism implements the Delete-and-Re-derive strategy with a truth maintenance system, and can help to reduce unnecessary over-deletion and re-derivation in stream reasoning and to improve its efficiency. As a whole, the thesis develops a worst-case tractable, guaranteed sound, conditionally complete and empirically high-recall reasoning solution for both static and dynamic ontologies in expressive DLs. Some techniques presented in the thesis can also be used to improve the performance and/or completeness of other existing reasoning solutions. The results can further be generalised and extended to support a wider range of knowledge representation formalisms, especially when a consequence-based algorithm is available.
APA, Harvard, Vancouver, ISO, and other styles
2

Coleman, Joseph William. "Constructing a tractable reasoning framework upon a fine-grained structural operational semantics." Thesis, University of Newcastle upon Tyne, 2008. http://hdl.handle.net/10443/898.

Full text
Abstract:
The primary focus of this thesis is the semantic gap between a fine-grained structural operational semantics and a set of rely/guarantee-style development rules. The semantic gap is bridged by considering the development rules to be a part of the same logical framework as the operational semantics, and a set of soundness proofs show that the development rules, though making development easier for a developer, do not add any extra power to the logical framework as a whole. The soundness proofs given are constructed to take advantage of the structural nature of the language and its semantics; this allows for the addition of new development rules in a modular fashion. The particular language semantics allows for very fine-grained concurrency. The language itself includes a construct for nested parallel execution of statements, and the semantics is written so that statements can interfere with each other between individual variable reads. The language also includes an atomic block construct for which the semantics is an embodiment of a form of software transactional memory. The inclusion of the atomic construct helps illustrate the inherent expressive weakness present in the rely/guarantee rules with respect to termination properties. As such, two development rules are proposed for the atomic construct, one of which has serious restrictions in its application, and another for which the termination property does not hold.
APA, Harvard, Vancouver, ISO, and other styles
3

Broxvall, Mathias. "A Study in the Computational Complexity of Temporal Reasoning." Doctoral thesis, Linköping : Univ, 2002. http://www.ep.liu.se/diss/science_technology/07/79/index.html.

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

Suntisrivaraporn, Boontawee. "Polynomial-Time Reasoning Support for Design and Maintenance of Large-Scale Biomedical Ontologies." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2009. http://nbn-resolving.de/urn:nbn:de:bsz:14-ds-1233830966436-59282.

Full text
Abstract:
Description Logics (DLs) belong to a successful family of knowledge representation formalisms with two key assets: formally well-defined semantics which allows to represent knowledge in an unambiguous way and automated reasoning which allows to infer implicit knowledge from the one given explicitly. This thesis investigates various reasoning techniques for tractable DLs in the EL family which have been implemented in the CEL system. It suggests that the use of the lightweight DLs, in which reasoning is tractable, is beneficial for ontology design and maintenance both in terms of expressivity and scalability. The claim is supported by a case study on the renown medical ontology SNOMED CT and extensive empirical evaluation on several large-scale biomedical ontologies.
APA, Harvard, Vancouver, ISO, and other styles
5

Suntisrivaraporn, Boontawee. "Polynomial-Time Reasoning Support for Design and Maintenance of Large-Scale Biomedical Ontologies." Doctoral thesis, Technische Universität Dresden, 2008. https://tud.qucosa.de/id/qucosa%3A23678.

Full text
Abstract:
Description Logics (DLs) belong to a successful family of knowledge representation formalisms with two key assets: formally well-defined semantics which allows to represent knowledge in an unambiguous way and automated reasoning which allows to infer implicit knowledge from the one given explicitly. This thesis investigates various reasoning techniques for tractable DLs in the EL family which have been implemented in the CEL system. It suggests that the use of the lightweight DLs, in which reasoning is tractable, is beneficial for ontology design and maintenance both in terms of expressivity and scalability. The claim is supported by a case study on the renown medical ontology SNOMED CT and extensive empirical evaluation on several large-scale biomedical ontologies.
APA, Harvard, Vancouver, ISO, and other styles
6

Liu, Yongmei. "Tractable reasoning in incomplete first-order knowledge bases /." 2006. http://link.library.utoronto.ca/eir/EIRdetail.cfm?Resources__ID=442431&T=F.

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

Givan, Robert, and David McAllester. "Tractable Inference Relations." 1991. http://hdl.handle.net/1721.1/5969.

Full text
Abstract:
We consider the concept of local sets of inference rules. Locality is a syntactic condition on rule sets which guarantees that the inference relation defined by those rules is polynomial time decidable. Unfortunately, determining whether a given rule set is local can be difficult. In this paper we define inductive locality, a strengthening of locality. We also give a procedure which can automatically recognize the locality of any inductively local rule set. Inductive locality seems to be more useful that the earlier concept of strong locality. We show that locality, as a property of rule sets, is undecidable in general.
APA, Harvard, Vancouver, ISO, and other styles
8

McAllester, David. "Observations on Cognitive Judgments." 1991. http://hdl.handle.net/1721.1/5972.

Full text
Abstract:
It is obvious to anyone familiar with the rules of the game of chess that a king on an empty board can reach every square. It is true, but not obvious, that a knight can reach every square. Why is the first fact obvious but the second fact not? This paper presents an analytic theory of a class of obviousness judgments of this type. Whether or not the specifics of this analysis are correct, it seems that the study of obviousness judgments can be used to construct integrated theories of linguistics, knowledge representation, and inference.
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Tractable reasoning"

1

Andreas, Holger. Dynamic Tractable Reasoning. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-36233-1.

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

Cadoli, Marco. Tractable Reasoning in Artificial Intelligence. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. http://dx.doi.org/10.1007/3-540-60058-2.

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

Tractable reasoning in artificial intelligence. Berlin: Springer-Verlag, 1995.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Selman, Bart. Tractable default reasoning. 1991.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

Liu, Yongmei. Tractable reasoning in incomplete first-order knowledge bases. 2006.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Wilson, Mark. Physics Avoidance. Oxford University Press, 2017. http://dx.doi.org/10.1093/oso/9780198803478.001.0001.

Full text
Abstract:
“Physics avoidance” refers to the fact that we frequently cannot reason about nature in the straightforward manner we anticipate, but must seek alternate policies to address the questions we want answered in a tractable way. Within both science and everyday life, we find ourselves tacitly relying upon thought processes that reach useful answers in opaque and roundabout manners. Conceptual innovators are often puzzled by the techniques they develop, when they stumble across reasoning patterns that are easy to implement but difficult to justify. But simple techniques frequently rest upon complex foundations—a young magician learns how to execute a card guessing trick without understanding how its progressive steps squeeze in on a correct answer. As we collectively improve our inferential skills in this evolving manner, we often wander into unfamiliar explanatory landscapes in which simple words encode physical information in complex and unanticipated ways. We have learned how to reach better conclusions, but we have become baffled by our successes. At its best, philosophical reflection illuminates the natural developmental processes that generate these confusions. But a number of widely shared methodological presumptions currently operate to opposite effect—they obscure the very tactics that advance our descriptive capacities. To correct these misapprehensions, sharper diagnostic tools are wanted. The nine new essays within this collection illustrate this need for finer discriminations through a range of informative cases of historical and contemporary significance.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Tractable reasoning"

1

Andreas, Holger. "Defeasible Reasoning." In Dynamic Tractable Reasoning, 67–78. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-36233-1_4.

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

Andreas, Holger. "Introduction." In Dynamic Tractable Reasoning, 1–19. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-36233-1_1.

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

Andreas, Holger. "Frames." In Dynamic Tractable Reasoning, 23–48. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-36233-1_2.

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

Andreas, Holger. "Belief Revision." In Dynamic Tractable Reasoning, 49–65. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-36233-1_3.

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

Andreas, Holger. "Postulates for Structuralism." In Dynamic Tractable Reasoning, 81–96. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-36233-1_5.

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

Andreas, Holger. "Structuralist Belief Revision." In Dynamic Tractable Reasoning, 97–108. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-36233-1_6.

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

Andreas, Holger. "Truth Maintenance." In Dynamic Tractable Reasoning, 109–51. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-36233-1_7.

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

Andreas, Holger. "Frame Logic." In Dynamic Tractable Reasoning, 153–93. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-36233-1_8.

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

Andreas, Holger. "Conclusions." In Dynamic Tractable Reasoning, 195–97. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-36233-1_9.

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

Dunin-Kęplicz, Barbara, Andrzej Szałas, and Rineke Verbrugge. "Tractable Reasoning about Group Beliefs." In Engineering Multi-Agent Systems, 328–50. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-14484-9_17.

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

Conference papers on the topic "Tractable reasoning"

1

Artale, A., R. Kontchakov, C. Lutz, F. Wolter, and M. Zakharyaschev. "Temporalising Tractable Description Logics." In 14th International Symposium on Temporal Representation and Reasoning (TIME'07). IEEE, 2007. http://dx.doi.org/10.1109/time.2007.62.

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

Chekol, Melisachew Wudage, and Heiner Stuckenschmidt. "Tractable reasoning in probabilistic OWL profiles." In SAC 2018: Symposium on Applied Computing. New York, NY, USA: ACM, 2018. http://dx.doi.org/10.1145/3167132.3167229.

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

Tan, Xing, and Michael Gruninger. "Towards tractable reasoning on temporal projection problems." In 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems (ICIS 2009). IEEE, 2009. http://dx.doi.org/10.1109/icicisys.2009.5358396.

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

Shi, Weijia, Andy Shih, Adnan Darwiche, and Arthur Choi. "On Tractable Representations of Binary Neural Networks." In 17th International Conference on Principles of Knowledge Representation and Reasoning {KR-2020}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/kr.2020/91.

Full text
Abstract:
We consider the compilation of a binary neural network’s decision function into tractable representations such as Ordered Binary Decision Diagrams (OBDDs) and Sentential Decision Diagrams (SDDs). Obtaining this function as an OBDD/SDD facilitates the explanation and formal verification of a neural network’s behavior. First, we consider the task of verifying the robustness of a neural network, and show how we can compute the expected robustness of a neural network, given an OBDD/SDD representation of it. Next, we consider a more efficient approach for compiling neural networks, based on a pseudo-polynomial time algorithm for compiling a neuron. We then provide a case study in a handwritten digits dataset, highlighting how two neural networks trained from the same dataset can have very high accuracies, yet have very different levels of robustness. Finally, in experiments, we show that it is feasible to obtain compact representations of neural networks as SDDs.
APA, Harvard, Vancouver, ISO, and other styles
5

Wałęga, Przemysław A., Bernardo Cuenca Grau, Mark Kaminski, and Egor V. Kostylev. "Tractable Fragments of Datalog with Metric Temporal Operators." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/266.

Full text
Abstract:
We study the data complexity of reasoning for several fragments of MTL - an extension of Datalog with metric temporal operators over the rational numbers. Reasoning in the full MTL language is PSPACE-complete, which handicaps its application in practice. To achieve tractability we first study the core fragment, which disallows conjunction in rule bodies, and show that reasoning remains PSPACE-hard. Intractability prompts us to also limit the kinds of temporal operators allowed in rules, and we propose a practical core fragment for which reasoning becomes TC0-complete. Finally, we show that this fragment can be extended by allowing linear conjunctions in rule bodies, where at most one atom can be intensional (IDB); we show that the resulting fragment is NL-complete, and hence no harder than plain linear Datalog.
APA, Harvard, Vancouver, ISO, and other styles
6

Souza, Marlo, Alvaro Moreira, and Renata Vieira. "Tractable Reasoning about Agent Programming in Dynamic Preference Logic." In 2018 7th Brazilian Conference on Intelligent Systems (BRACIS). IEEE, 2018. http://dx.doi.org/10.1109/bracis.2018.00070.

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

Belardinelli, Francesco, Wojciech Jamroga, Damian Kurpiewski, Vadim Malvone, and Aniello Murano. "Strategy Logic with Simple Goals: Tractable Reasoning about Strategies." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/13.

Full text
Abstract:
In this paper we introduce Strategy Logic with simple goals (SL[SG]), a fragment of Strategy Logic that strictly extends the well-known Alternating-time Temporal Logic ATL by introducing arbitrary quantification over the agents' strategies. Our motivation comes from game-theoretic applications, such as expressing Stackelberg equilibria in games, coercion in voting protocols, as well as module checking for simple goals. Most importantly, we prove that the model checking problem for SL[SG] is PTIME-complete, the same as ATL. Thus, the extra expressive power comes at no computational cost as far as verification is concerned.
APA, Harvard, Vancouver, ISO, and other styles
8

Audemard, Gilles, Frédéric Koriche, and Pierre Marquis. "On Tractable XAI Queries based on Compiled Representations." In 17th International Conference on Principles of Knowledge Representation and Reasoning {KR-2020}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/kr.2020/86.

Full text
Abstract:
One of the key purposes of eXplainable AI (XAI) is to develop techniques for understanding predictions made by Machine Learning (ML) models and for assessing how much reliable they are. Several encoding schemas have recently been pointed out, showing how ML classifiers of various types can be mapped to Boolean circuits exhibiting the same input-output behaviours. Thanks to such mappings, XAI queries about classifiers can be delegated to the corresponding circuits. In this paper, we define new explanation and/or verification queries about classifiers. We show how they can be addressed by combining queries and transformations about the associated Boolean circuits. Taking advantage of previous results from the knowledge compilation map, this allows us to identify a number of XAI queries that are tractable provided that the circuit has been first turned into a compiled representation.
APA, Harvard, Vancouver, ISO, and other styles
9

Chen, Hubie, and Michal Wrona. "Guarded Ord-Horn: A Tractable Fragment of Quantified Constraint Satisfaction." In 2012 19th International Symposium on Temporal Representation and Reasoning (TIME). IEEE, 2012. http://dx.doi.org/10.1109/time.2012.19.

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

Schwering, Christoph. "A Reasoning System for a First-Order Logic of Limited Belief." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/173.

Full text
Abstract:
Logics of limited belief aim at enabling computationally feasible reasoning in highly expressive representation languages. These languages are often dialects of first-order logic with a weaker form of logical entailment that keeps reasoning decidable or even tractable. While a number of such logics have been proposed in the past, they tend to remain for theoretical analysis only and their practical relevance is very limited. In this paper, we aim to go beyond the theory. Building on earlier work by Liu, Lakemeyer, and Levesque, we develop a logic of limited belief that is highly expressive but remains decidable in the first-order and tractable in the propositional case and exhibits some characteristics that make it attractive for an implementation. We introduce a reasoning system that employs this logic as representation language and present experimental results that showcase the benefit of limited belief.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Tractable reasoning' 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