On the orthographic dimension of definable sets

Citation
S. Cosmadakis et al., On the orthographic dimension of definable sets, INF PROCESS, 79(3), 2001, pp. 141-145
Citations number
7
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
79
Issue
3
Year of publication
2001
Pages
141 - 145
Database
ISI
SICI code
0020-0190(20010731)79:3<141:OTODOD>2.0.ZU;2-F
Abstract
A formula psi (x(1),....x(n)) conforms to a partition P of {x(1)...., x(n)) if it is equivalent to a Boolean combination of formulae that do not have free variables from more than one block of P. We show that if psi conforms to two partitions P-1 and P-2, it also conforms to their greatest lower bou nd in the partition lattice. As a corollary, we obtain that the concept of orthographic dimension of a constraint-definable set, introduced in the fie ld of constraint databases, is well-defined. (C) 2001 Elsevier Science B.V. All rights reserved.