Two versions of a set theoretic triangle open-language are considered as theoretical prototypes for "nested" data base query language where data base states and queries are represented, respectively, as hereditarily-finite (HF) sets and set theoretic operations. It is shown that these versions correspond exactly to (N/D)LOGSPACE computability over HF, respectively. Such languages over sets, capturing also PTIME, were introduced in previous works, however, descriptions of LOGSPACE over HF [A.Lisitsa and V.Sazonov, TCS (175) 1 (1997) pp. 183-222] were not completely satisfactory. Here we overcome the drawbacks of the previous approaches due to some new partial result on definability of a linear ordering over finite extensional acyclic graphs and present a unified and simplified approach.
展开▼
