Zobrazeno 1 - 10
of 335
pro vyhledávání: '"03c13"'
Autor:
Bodirsky, Manuel, Guzmán-Pro, Santiago
Many computational problems can be modelled as the class of all finite relational structures $\mathbb A$ that satisfy a fixed first-order sentence $\phi$ hereditarily, i.e., we require that every substructure of $\mathbb A$ satisfies $\phi$. In this
Externí odkaz:
http://arxiv.org/abs/2411.10860
Autor:
Koponen, Vera, Tousinejad, Yasmin
We consider a sequence $\mathbf{T} = (\mathcal{T}_n : n \in \mathbb{N}^+)$ of trees $\mathcal{T}_n$ where, for some $\Delta \in \mathbb{N}^+$ every $\mathcal{T}_n$ has height at most $\Delta$ and as $n \to \infty$ the minimal number of children of a
Externí odkaz:
http://arxiv.org/abs/2410.11775
A relational structure R is ultrahomogeneous if every isomorphism of finite induced substructures of R extends to an automorphism of R. We classify the ultrahomogeneous finite binary relational structures with one asymmetric binary relation and arbit
Externí odkaz:
http://arxiv.org/abs/2408.07162
We develop a general framework (multidimensional asymptotic classes, or m.a.c.s) for handling classes of finite first order structures with a strong uniformity condition on cardinalities of definable sets: The condition asserts that definable familie
Externí odkaz:
http://arxiv.org/abs/2408.00102
The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. It can be solved in time polynomial in the domain size for sentences from the two-variable f
Externí odkaz:
http://arxiv.org/abs/2407.11877
It is often convenient to represent a process for randomly generating a graph as a graphon. (More precisely, these give \emph{vertex exchangeable} processes -- those processes in which each vertex is treated the same way.) Other structures can be tre
Externí odkaz:
http://arxiv.org/abs/2406.08195
The description complexity of a model is the length of the shortest formula that defines the model. We study the description complexity of unary structures in first-order logic FO, also drawing links to semantic complexity in the form of entropy. The
Externí odkaz:
http://arxiv.org/abs/2406.02108
Autor:
Dawar, Anuj, Eleftheriadis, Ioannis
We revisit the work studying homomorphism preservation for first-order logic in sparse classes of structures initiated in [Atserias et al., JACM 2006] and [Dawar, JCSS 2010]. These established that first-order logic has the homomorphism preservation
Externí odkaz:
http://arxiv.org/abs/2405.10887
Autor:
Carr, James
A canonical result in model theory is the homomorphism preservation theorem which states that a first-order formula is preserved under homomorphisms on all structures if and only if it is equivalent to an existential-positive formula, standardly prov
Externí odkaz:
http://arxiv.org/abs/2403.00217
Autor:
Koponen, Vera
We consider finite relational signatures $\tau \subseteq \sigma$, a sequence of finite base $\tau$-structures $(\mathcal{B}_n : n \in \mathbb{N})$ the cardinalities of which tend to infinity and such that there is a fixed finite upper bound of the de
Externí odkaz:
http://arxiv.org/abs/2401.04802