Symblicit algorithms for mean-payoff and shortest path in monotonic Markov decision processes

When treating Markov decision processes (MDPs) with large state spaces, using explicit representations quickly becomes unfeasible. Lately, Wimmer et al. have proposed a so-called symblicit algorithm for the synthesis of optimal strategies in MDPs, in the quantitative setting of expected mean-payoff. This algorithm, based on the strategy iteration algorithm of Howard and Veinott, efficiently combines symbolic and explicit data structures, and uses binary decision diagrams as symbolic representation. The aim of this paper is to show that the new data structure of pseudo-Antichains (an extension of Antichains) provides another interesting alternative, especially for the class of monotonic MDPs. We design efficient pseudo-Antichain based symblicit algorithms (with open source implementations) for two quantitative settings: the expected mean-payoff and the stochastic shortest path. For two practical applications coming from automated planning and $$\mathsf {LTL}$$ LTL synthesis, we report promising experimental results w.r.t. both the run time and the memory consumption. We also show that a variant of pseudo-Antichains allows to handle the infinite state spaces underlying the qualitative verification of probabilistic lossy channel systems.

Antichain based qbf solving

We consider the problem of QBF solving viewed as a reachability problem in an exponential And-Or graph. Antichain-based algorithms for reachability analysis in large graphs exploit certain subsumption relations to leverage the inherent structure of the explored graph in order to reduce the effect of state explosion, with high performance in practice.

In this paper, we propose simple notions of subsumption induced by the structural properties of the And-Or graphs for QBF solving. Subsumption is used to reduce the size of the search tree, and to define compact representations of certificates (in the form of Antichains) both for positive and negative instances of QBF. We show that efficient exploration of the reduced search tree essentially relies on solving variants of Max-SAT and Min-SAT. Preliminary stand-alone experiments of this algorithm show that the Antichain-based approach is promising.

ATVA – Antichain-based QBF solving

We consider the problem of QBF solving viewed as a reachability problem in an exponential And-Or graph. Antichain-based algorithms for reachability analysis in large graphs exploit certain subsumption relations to leverage the inherent structure of the explored graph in order to reduce the effect of state explosion, with high performance in practice.

In this paper, we propose simple notions of subsumption induced by the structural properties of the And-Or graphs for QBF solving. Subsumption is used to reduce the size of the search tree, and to define compact representations of certificates (in the form of Antichains) both for positive and negative instances of QBF. We show that efficient exploration of the reduced search tree essentially relies on solving variants of Max-SAT and Min-SAT. Preliminary stand-alone experiments of this algorithm show that the Antichain-based approach is promising.

Short Antichains in root systems, semi-Catalan arrangements, and B -stable subspaces

Let G be a complex simple algebraic group with Lie algebra g. Fix a Borel subalgebra b. An ideal of b is called ad-nilpotent, if it is contained in [b, b]. The goal of this paper is to present a refinement of the enumerative theory of ad-nilpotent ideals in the case, where g has roots of different length. Let Ad denote the set of all ad-nilpotent ideals of b. Any c ∈ Ad is completely determined by the corresponding set of roots. The minimal roots in this set are called the generators of an ideal. The collection of generators of an ideal forms an Antichain in the poset of positive roots, and the whole theory can be expressed in the combinatorial language, in terms of Antichains. An Antichain is called strictly positive, if it contains no simple roots. Enumerative results for all and strictly positive Antichains were recently obtained in the work of Athanasiadis, Cellini–Papi, Sommers, and this author [1–4, 9, 13]. There are two different theoretical approaches to describing (enumerating) Antichains. The first approach consists of constructing a bijection between Antichains and the coroot lattice points lying in a certain simplex. An important intermediate step here is a bijection between Antichains and the so-called minimal elements of the affine Weyl group, Ŵ . It turns out that the simplex obtained is “equivalent” to a dilation of the fundamental alcove of Ŵ , so that the problem of counting the coroot lattice points in it can be resolved. For strictly positive Antichains, one constructs another bijection and another simplex, and the respective elements of Ŵ are called maximal; yet, everything is quite similar. The second approach uses the Shi bijection between the ad-nilpotent ideals (or Antichains) and the dominant regions of the Catalan arrangement. Under this bijection, the strictly positive Antichains correspond to the bounded regions. There is a powerful result of Zaslavsky allowing one to compute the number of all and bounded regions, if the characteristic polynomial of the arrangement is known. Since the characteristic polynomial of the Catalan arrangement was recently computed in [1], the result follows. If g has roots of different length, one can distinguish the length of elements occurring in Antichains. We say that an Antichain is short, if it consists of only short roots. This notion has a natural representation-theoretic incarnation: the short Antichains are in

Short Antichains in root systems, semi-Catalan arrangements, and B-stable subspaces

Let $\be$ be a Borel subalgebra of a complex simple Lie algebra $\g$. An ideal of $\be$ is called ad-nilpotent, if it is contained in $[\be,\be]$. The generators of an ad-nilpotent ideal give rise to an Antichain in the poset of positive roots, and the whole theory can be expressed in a combinatorial fashion, in terms of Antichains. The aim of this paper is to present a refinement of the enumerative theory of ad-nilpotent ideals for the case in which $\g$ has roots of different length. An Antichain is called short, if it consists of short roots. We obtain, for short Antichains, analogues of all results known for the usual Antichains.

quasi Antichain chermak delgado lattices of finite groups

The Chermak–Delgado lattice of a finite group is a dual, modular sublattice of the subgroup lattice of the group. This paper considers groups with a quasi-Antichain interval in the Chermak–Delgado lattice, ultimately proving that if there is a quasi-Antichain interval between subgroups L and H with L ≤ H then there exists a prime p such that H/L is an elementary abelian p-group and the number of atoms in the quasi-Antichain is one more than a power of p. In the case where the Chermak–Delgado lattice of the entire group is a quasi-Antichain, the relationship between the number of abelian atoms and the prime p is examined; additionally, several examples of groups with a quasi-Antichain Chermak–Delgado lattice are constructed.

Quasi-Antichain Chermak–Delgado lattices of finite groups

The Chermak–Delgado lattice of a finite group is a dual, modular sublattice of the subgroup lattice of the group. This paper considers groups with a quasi-Antichain interval in the Chermak–Delgado lattice, ultimately proving that if there is a quasi-Antichain interval between subgroups L and H with L ≤  H then there exists a prime p such that H / L is an elementary abelian p -group and the number of atoms in the quasi-Antichain is one more than a power of p . In the case where the Chermak–Delgado lattice of the entire group is a quasi-Antichain, the relationship between the number of abelian atoms and the prime p is examined; additionally, several examples of groups with a quasi-Antichain Chermak–Delgado lattice are constructed.

Quasi-Antichain Chermak-Delgado Lattices of Finite Groups

The Chermak-Delgado lattice of a finite group is a dual, modular sublattice of the subgroup lattice of the group. This paper considers groups with a quasi-Antichain interval in the Chermak-Delgado lattice, ultimately proving that if there is a quasi-Antichain interval between $L$ and $H$ with $L \leq H$ then there exists a prime $p$ such that the quotient $H / L$ is an elementary abelian $p$-group and the number of atoms in the quasi-Antichain is one more than a power of $p$. In the case where the Chermak-Delgado lattice of the entire group is a quasi-Antichain, the relationship between the number of abelian atoms and the prime $p$ is examined; additionally several examples of group with a quasi-Antichain Chermak-Delgado lattice are constructed.