On Locally Presented Posets
On Locally Presented Posets
复制标题
关于本地呈现的姿势
DOI：
10.1016/0304-3975(90)90125-2
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
M. Talamo
中科院分区：
文献类型：
--
作者：
G. Gambosi;J. Nesetril;M. Talamo
本文引入偏序集的局部可表示性的概念，并引入布尔维数的概念，作为经典Dushnik-Miller维数的推广。从空间和时间复杂度的角度来看，这样的概念似乎代表了一个有效编码偏序集和传递闭包的dags的强大工具。作为该理论的一个应用，给出了偏序集的编码：特别地，引入了平面dag类的一个子类的有效编码。
In this paper, the concept of local presentability of posets is introduced, together with the related notion of boolean dimension, as an extension of the classic Dushnik-Miller dimension. Such a concept seems to represent a powerful tool for the efficient encoding of poset and transitive closure of dags, from the point of view of both space and time complexity. Encodings of some classes of posets are presented as an application of the theory: in particular, an efficient encoding of a subclass of the class of planar dags is introduced.