A finite relation algebra with undecidable network satisfaction problem
Logic Journal of IGPLPublished 1 July 1999
Robin Hirsch
Citations16
SJR quartileQ2
SJR score0.26
SNIP0.70
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
Journal Article A finite relation algebra with undecidable network satisfaction problem Get access R Hirsch R Hirsch Department of Computer Science, University College London, Gower Street, London WC1, UK. E-mail: [email protected] Search for other works by this author on: Oxford Academic Google Scholar Logic Journal of the IGPL, Volume 7, Issue 4, July 1999, Pages 547–554, https://doi.org/10.1093/jigpal/7.4.547 Published: 01 July 1999
Keywords
Computer Science
Communications of the ACMMaintaining knowledge about temporal intervals
7,550 Citations1983James F. Allen
An interval-based temporal logic is introduced, together with a computationally effective reasoning algorithm based on constraint propagation, which is notable in offering a delicate balance between space and time.
Artificial IntelligenceTowards a general theory of action and time
2,562 Citations1984James F. Allen
A formalism for reasoning about actions that is based on a temporal logic allows a much wider range of actions to be described than with previous approaches such as the situation calculus and a framework for planning in a dynamic world with external events and multiple agents is suggested.
Artificial IntelligenceTemporal constraint networks
1,800 Citations1991Rina Dechter, Itay Meiri +1 more
It is shown that the STP, which subsumes the major part of Vilain and Kautz's point algebra, can be solved in polynomial time and the applicability of path consistency algorithms as preprocessing of temporal problems is studied, to demonstrate their termination and bound their complexities.
Constraint propagation algorithms for temporal reasoning
643 Citations1986Marc Vilain, Henry Kautz
Computing the consequences of temporal assertions is shown to be computationally intractable in the interval-based representation, but not in the point-based one, but a fragment of the interval language can be expressed using the point language and benefits from the tractability of the latter.
Journal of the ACMOn binary constraint problems
190 Citations1994Peter B. Ladkin, Roger D. Maddux
The concepts of binary constraint satisfaction problems can be naturally generalized to the relation algebras of Tarski, and a class of examples over a fixed finite algebra on which all iterative local algorithms, whether parallel or sequential, must take quadratic time is given.
Journal of Symbolic LogicStep by step – Building representations in algebraic logic
65 Citations1997Robin Hirsch, Ian Hodkinson
A simple proof that the perfect extension of a representable relation algebra is completely representable is presented, and an important open problem from algebraic logic is addressed by devising another two-player game, and using it to derive equational axiomatisations for the classes of all representingable relation algebras and representable cylindric algeBRas.
Memoirs of the American Mathematical SocietyDecision problems for equational theories of relation algebras
37 Citations1997Hajnal Andréka, Steven Givant +1 more
In 1942, Tarski proved that all of classical mathematics could be developed within the framework of the equational theory of relation algebras first-order theories that are strong enough to form a basis for the development of mathematics, in particular, set theories and number theories.