  Cardinality-based feature models permit to select multiple copies of the same
feature, thus generalizing the notion of product configurations from subsets of
Boolean features to multisets of feature instances. This increased
expressiveness shapes a-priori infinite and non-convex configuration spaces,
which renders established solution-space mappings based on Boolean presence
conditions insufficient for cardinality-based feature models. To address this
issue, we propose weighted automata over featured multiset semirings as a novel
behavioral variability modeling formalism for cardinality-based feature models.
The formalism uses multisets over features as a predefined semantic domain for
transition weights. It permits to use any algebraic structure forming a proper
semiring on multisets to aggregate the weights traversed along paths to map
accepted words to multiset configurations. In particular, tropical semirings
constitute a promising sub-class with a reasonable trade-off between
expressiveness and computational tractability of canonical analysis problems.
The formalism is strictly more expressive than featured transition systems, as
it enables upper-bound multiplicity constraints depending on the length of
words. We provide a tool implementation of the behavioral variability model and
present preliminary experimental results showing applicability and
computational feasibility of the proposed approach.
