Tarskian set constraints
- 24 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 138-147
- https://doi.org/10.1109/lics.1996.561313
Abstract
We investigate set constraints over set expressions with Tarskian functional and relational operations. Unlike the Herbrand constructor symbols used in recent set constraint formalisms, the meaning of a Tarskian function symbol is interpreted in an arbitrary first order structure. We show that satisfiability of Tarskian set constraints is decidabl e in nondeterministic doubly exponential time. We also give complexity results and open problems for various extension s of the language.Keywords
This publication has 25 references indexed in Scilit:
- Logic programs as types for logic programsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A decision procedure for a class of set constraintsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Decidability of Systems of Set Constraints with Negative ConstraintsInformation and Computation, 1995
- Taxonomic syntax for first order inferenceJournal of the ACM, 1993
- Attributive concept descriptions with complementsArtificial Intelligence, 1991
- A finite presentation theorem for approximating logic programsPublished by Association for Computing Machinery (ACM) ,1990
- Varieties of complex algebrasAnnals of Pure and Applied Logic, 1989
- An automata theoretic decision procedure for the propositional mu-calculusInformation and Computation, 1989
- The complexity of tree automata and logics of programsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Propositional dynamic logic of regular programsJournal of Computer and System Sciences, 1979