Logic of temporal attribute implications

DOI10.1007/S10472-016-9526-6zbMATH Open1409.68283arXiv1412.3633OpenAlexW2963301870MaRDI QIDQ2364366FDOQ2364366

Vilem Vychodil, Jan Triska

Publication date: 19 July 2017

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Abstract: We study logic for reasoning with if-then formulas describing dependencies between attributes of objects which are observed in consecutive points in time. We introduce semantic entailment of the formulas, show its fixed-point characterization, investigate closure properties of model classes, present an axiomatization and prove its completeness, and investigate alternative axiomatizations and normalized proofs. We investigate decidability and complexity issues of the logic and prove that the entailment problem is NP-hard and belongs to EXPSPACE. We show that by restricting to predictive formulas, the entailment problem is decidable in pseudo-linear time.

Full work available at URL: https://arxiv.org/abs/1412.3633

zbMATH Keywords

fixed pointcomplete axiomatizationfunctional dependencyattribute implicationtemporal semanticsentailment problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30) Logic in artificial intelligence (68T27)

Cites Work

• Title not available (Why is that?)
• Extending inclusion dependencies with conditions
• Modal logic
• Title not available (Why is that?)
• Title not available (Why is that?)
• Metamathematics of fuzzy logic
• A lattice-theoretical fixpoint theorem and its applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A relational model of data for large shared data banks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Machine-Oriented Logic Based on the Resolution Principle
• On a generalization of quantifiers
• The implication problem for `closest node' functional dependencies in complete XML documents
• Functional Dependencies in a Relational Database and Propositional Logic
• Interval-based temporal functional dependencies: specification and verification
• A relation-algebraic approach to the ``Hoare logic of functional dependencies
• Title not available (Why is that?)
• Two Basic Algorithms in Concept Analysis
• Non-deterministic ideal operators: an adequate tool for formalization in data bases
• On functional dependencies in \(q\)-Horn theories
• Reasoning about time in the situation calculus
• Logic of temporal attribute implications
• Inter-transactional association rules for multi-dimensional contexts for prediction and their application to studying meteorological data
• Title not available (Why is that?)
• Conceptual Structures at Work
• Reasoning about functional and full hierarchical dependencies over partial relations
• The Complexity of Clausal Fragments of LTL
• Characterizing functional dependencies in formal concept analysis with pattern structures
• Logical foundations for more expressive declarative temporal logic programming languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Detection and exploitation of functional dependencies for model generation

Cited In (4)

• Minimal bases of temporal attribute implications
• Logic of temporal attribute implications
• Closure structures parameterized by systems of isotone Galois connections
• Evolution of objects and concepts

Uses Software

• PDDL

This page was built for publication: Logic of temporal attribute implications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2364366)