Recent zbMATH articles in MSC 06A06https://www.zbmath.org/atom/cc/06A062021-04-16T16:22:00+00:00WerkzeugA new characterization of \(\mathcal{V} \)-posets.https://www.zbmath.org/1456.060012021-04-16T16:22:00+00:00"Cooper, Joshua"https://www.zbmath.org/authors/?q=ai:cooper.joshua-n"Gartland, Peter"https://www.zbmath.org/authors/?q=ai:gartland.peter"Whitlatch, Hays"https://www.zbmath.org/authors/?q=ai:whitlatch.haysThe paper defines a finite poset \(P\) to be ``autonomous''
if there exists a directed acyclic graph \(D\) with
adjacency matrix \(U\) whose transitive closure is \(P\),
with the property that any total ordering of the vertices of
\(D\) so that Gaussian elimination of \(U^tU\)
proceeds without row swaps is a linear extension of \(P\).
The main theorem of the paper is that a finite poset is autonomous
if and only if it is induced \(N\)-free and induced bowtie-free.
This class of posets has a ``series-parallel''
type of characterization:
by a theorem of \textit{T. Hasebe} and \textit{S. Tsujie} [J. Algebr. Comb. 46, No. 3--4, 499--515 (2017; Zbl 1423.06011)] the
class of finite induced \(N\)-free and induced bowtie-free
posets is the smallest isomorphism-closed class of posets
which (i) contains the \(1\)-element poset,
(ii) is closed under the formation of disjoint union, and
(iii) is closed under adjoining new least or largest elements.
Reviewer: Keith Kearnes (Boulder)Quantified conjunctive queries on partially ordered sets.https://www.zbmath.org/1456.680962021-04-16T16:22:00+00:00"Bova, Simone"https://www.zbmath.org/authors/?q=ai:bova.simone"Ganian, Robert"https://www.zbmath.org/authors/?q=ai:ganian.robert"Szeider, Stefan"https://www.zbmath.org/authors/?q=ai:szeider.stefanSummary: We study the computational problem of checking whether a quantified conjunctive query (a first-order sentence built using only conjunction as Boolean connective) is true in a finite poset (a reflexive, antisymmetric, and transitive directed graph). We prove that the problem is already NP-hard on a certain fixed poset, and investigate structural properties of posets yielding fixed-parameter tractability when the problem is parameterized by the query. Our main algorithmic result is that model checking quantified conjunctive queries on posets of bounded width is fixed-parameter tractable (the width of a poset is the maximum size of a subset of pairwise incomparable elements). We complement our algorithmic result by complexity results with respect to classes of finite posets in a hierarchy of natural poset invariants, establishing its tightness in this sense.
For the entire collection see [Zbl 1318.68014].