| 1. |
- Ahlman, Ove, et al.
(författare)
-
Limit laws and automorphism groups of random nonrigid structures
- 2015
-
Ingår i: Journal of Logic and Analysis. - : Journal of Logic and Analysis. - 1759-9008. ; 7:2, s. 1-53
-
Tidskriftsartikel (refereegranskat)abstract
- A systematic study is made, for an arbitrary finite relational language with at least one symbol of arity at least 2, of classes of nonrigid finite structures. The well known results that almost all finite structures are rigid and that the class of finite structures has a zero-one law are, in the present context, the first layer in a hierarchy of classes of finite structures with increasingly more complex automorphism groups. Such a hierarchy can be defined in more than one way. For example, the kth level of the hierarchy can consist of all structures having at least k elements which are moved by some automorphism. Or we can consider, for any finite group G, all finite structures M such that G is a subgroup of the group of automorphisms of M; in this case the "hierarchy" is a partial order. In both cases, as well as variants of them, each "level" satisfies a logical limit law, but not a zero-one law (unless k = 0 or G is trivial). Moreover, the number of (labelled or unlabelled) n-element structures in one place of the hierarchy divided by the number of n-element structures in another place always converges to a rational number or to infinity as n -> infinity. All instances of the respective result are proved by an essentially uniform argument.
|
|
| 2. |
- Ahlman, Ove, et al.
(författare)
-
On sets with rank one in simple homogeneous structures
- 2015
-
Ingår i: Fundamenta Mathematicae. - : Institute of Mathematics, Polish Academy of Sciences. - 0016-2736 .- 1730-6329. ; 228, s. 223-250
-
Tidskriftsartikel (refereegranskat)abstract
- We study definable sets D of SU-rank 1 in Meq, where M is a countable homogeneous and simple structure in a language with finite relational vocabulary. Each such D can be seen as a 'canonically embedded structure', which inherits all relations on D which are definable in Meq, and has no other definable relations. Our results imply that if no relation symbol of the language of M has arity higher than 2, then there is a close relationship between triviality of dependence and D being a reduct of a binary random structure. Somewhat more precisely: (a) if for every n≥2, every n-type p(x1,...,xn) which is realized in D is determined by its sub-2-types q(xi,xj)⊆p, then the algebraic closure restricted to D is trivial; (b) if M has trivial dependence, then D is a reduct of a binary random structure.
|
|
| 3. |
- Ahlman, Ove, 1988-, et al.
(författare)
-
Random l-colourable structures with a pregeometry
- 2017
-
Ingår i: Mathematical logic quarterly. - : Wiley-VCH Verlagsgesellschaft. - 0942-5616 .- 1521-3870. ; 63:1-2, s. 32-58
-
Tidskriftsartikel (refereegranskat)abstract
- We study finite -colourable structures with an underlying pregeometry. The probability measure that is usedcorresponds to a process of generating such structures by which colours are first randomly assigned to all1-dimensional subspaces and then relationships are assigned in such a way that the colouring conditions aresatisfied but apart from this in a random way. We can then ask what the probability is that the resulting structure,where we now forget the specific colouring of the generating process, has a given property. With this measurewe get the following results: (1) A zero-one law. (2) The set of sentences with asymptotic probability 1 has anexplicit axiomatisation which is presented. (3) There is a formula ξ (x, y) (not directly speaking about colours)such that, with asymptotic probability 1, the relation “there is an -colouring which assigns the same colourto x and y” is defined by ξ (x, y). (4) With asymptotic probability 1, an -colourable structure has a unique-colouring (up to permutation of the colours).
|
|
| 4. |
- Koponen, Vera, 1968-, et al.
(författare)
-
Asymptotic elimination of partially continuous aggregation functions in directed graphical models
- 2023
-
Ingår i: Information and Computation. - : Elsevier. - 0890-5401 .- 1090-2651. ; 293
-
Tidskriftsartikel (refereegranskat)abstract
- For a finite and relational signature σ and finite domain D we consider the set of all σ-structures with domain D. On a probability distribution is determined by a so-called parametrized probabilistic graphical model, a concept studied in statistical relational artificial intelligence. We also consider a many valued logic, denoted PLA, with truth values in the unit interval for expressing queries. PLA uses aggregation functions, for example the arithmetic mean, geometric mean, maximum and minimum, instead of quantifiers. In this setting we prove that every formula of PLA with only admissible aggregation functions is asymptotically equivalent to a formula without aggregation functions, as the domain size tends to infinity. A corollary of this is a probabilistic convergence law for PLA-formulas with only admissible aggregation functions.
|
|
| 5. |
- Koponen, Vera, 1968-
(författare)
-
Binary primitive homogeneous simple structures
- 2017
-
Ingår i: Journal of Symbolic Logic (JSL). - : Cambridge University Press (CUP). - 0022-4812 .- 1943-5886. ; 82:1, s. 183-207
-
Tidskriftsartikel (refereegranskat)abstract
- Suppose that M is countable, binary, primitive, homogeneous, and simple. We prove that the SU-rank of the complete theory of M is 1 and hence 1-based. It follows that M is a random structure. The conclusion that M is a random structure does not hold if the binarity condition is removed, as witnessed by the generic tetrahedron-free 3-hypergraph. However, to show that the generic tetrahedron-free 3-hypergraph is 1-based requires some work (it is known that it has the other properties) since this notion is defined in terms of imaginary elements. This is partly why we also characterize equivalence relations which are definable without parameters in the context of omega-categorical structures with degenerate algebraic closure. Another reason is that such characterizations may be useful in future research about simple (nonbinary) homogeneous structures.
|
|
| 6. |
- Koponen, Vera, 1968-
(författare)
-
Binary simple homogeneous structures
- 2018
-
Ingår i: Annals of Pure and Applied Logic. - : Elsevier BV. - 0168-0072 .- 1873-2461. ; 169:12, s. 1335-1368
-
Tidskriftsartikel (refereegranskat)abstract
- We describe all binary simple homogeneous structures M in terms of ∅-definable equivalence relations on M, which “coordinatize” M and control dividing, and extension properties that respect these equivalence relations.
|
|
| 7. |
- Koponen, Vera, 1968-
(författare)
-
Binary simple homogeneous structures are supersimple with finite rank
- 2016
-
Ingår i: Proceedings of the American Mathematical Society. - : American Mathematical Society (AMS). - 0002-9939 .- 1088-6826. ; 144:4, s. 1745-1759
-
Tidskriftsartikel (refereegranskat)abstract
- Suppose that M is an infinite structure with finite relational vocabulary such that every relation symbol has arity at most 2. If M is simple and homogeneous, then its complete theory is supersimple with finite SU-rank which cannot exceed the number of complete 2-types over the empty set.
|
|
| 8. |
- Koponen, Vera, 1968-
(författare)
-
Conditional probability logic, lifted Bayesian networks, and almost sure quantifier elimination
- 2020
-
Ingår i: Theoretical Computer Science. - : Elsevier BV. - 0304-3975 .- 1879-2294. ; 848, s. 1-27
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce a formal logical language, called conditional probability logic (CPL), which extends first-order logic and which can express probabilities, conditional probabilities and which can compare conditional probabilities. Intuitively speaking, although formal details are different, CPL can express the same kind of statements as some languages which have been considered in the artificial intelligence community. We also consider a way of making precise the notion of lifted Bayesian network, where this notion is a type of (lifted) probabilistic graphical model used in machine learning, data mining and artificial intelligence. A lifted Bayesian network (in the sense defined here) determines, in a natural way, a probability distribution on the set of all structures (in the sense of first-order logic) with a common finite domain D. Our main result (Theorem 3.14) is that for every "noncritical" CPL-formula φ(x‾) there is a quantifier-free formula φ*(x‾) which is "almost surely" equivalent to φ(x‾) as the cardinality of D tends towards infinity. This is relevant for the problem of making probabilistic inferences on large domains D, because (a) the problem of evaluating, by "brute force", the probability of φ(x‾) being true for some sequence d‾ of elements from D has, in general, (highly) exponential time complexity in the cardinality of D, and (b) the corresponding probability for the quantifier-free φ*(x‾) depends only on the lifted Bayesian network and not on D. Some conclusions regarding the computational complexity of finding φ* are given in Remark 3.17. The main result has two corollaries, one of which is a convergence law (and zero-one law) for noncritial CPL-formulas.
|
|
| 9. |
- Koponen, Vera, 1968-
(författare)
-
Entropy of formulas
- 2009
-
Ingår i: Archive for mathematical logic. - : Springer. - 0933-5846 .- 1432-0665. ; 48:6, s. 515-522
-
Tidskriftsartikel (refereegranskat)abstract
- A probability distribution can be given to the set of isomorphism classes of models with universe {1, ..., n} of a sentence in first-order logic. We study the entropy of this distribution and derive a result from the 0-1 law for first-order sentences.
|
|
| 10. |
- Koponen, Vera, 1968-
(författare)
-
Homogeneous 1-based structures and interpretability in random structures
- 2017
-
Ingår i: Mathematical logic quarterly. - : Wiley-VCH Verlagsgesellschaft. - 0942-5616 .- 1521-3870. ; 63:1-2, s. 6-18
-
Tidskriftsartikel (refereegranskat)abstract
- Let V be a finite relational vocabulary in which no symbol has arity greater than 2. Let math formula be countable V-structure which is homogeneous, simple and 1-based. The first main result says that if math formula is, in addition, primitive, then it is strongly interpretable in a random structure. The second main result, which generalizes the first, implies (without the assumption on primitivity) that if math formula is “coordinatized” by a set with SU-rank 1 and there is no definable (without parameters) nontrivial equivalence relation on M with only finite classes, then math formula is strongly interpretable in a random structure.
|
|
