Title :
Tarskian set constraints
Author :
McAllester, David A. ; Givan, Robert ; Witty, Carl ; Kozen, Dexter
Author_Institution :
AT&T Bell Labs., Murray Hill, NJ, USA
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 decidable in nondeterministic doubly exponential time. We also give complexity results and open problems for various extensions of the language
Keywords :
algorithm theory; computability; formal logic; grammars; set theory; Herbrand constructor symbols; Tarskian functional operations; Tarskian relational operations; Tarskian set constraints; complexity results; first order structure; nondeterministic doubly exponential time; set constraint formalisms; set expressions; Application software; Artificial intelligence; Laboratories; Logic; Page description languages;
Conference_Titel :
Logic in Computer Science, 1996. LICS '96. Proceedings., Eleventh Annual IEEE Symposium on
Conference_Location :
New Brunswick, NJ
Print_ISBN :
0-8186-7463-6
DOI :
10.1109/LICS.1996.561313
