  The causal Markov condition (CMC) is a postulate that links observations to
causality. It describes the conditional independences among the observations
that are entailed by a causal hypothesis in terms of a directed acyclic graph.
In the conventional setting, the observations are random variables and the
independence is a statistical one, i.e., the information content of
observations is measured in terms of Shannon entropy. We formulate a
generalized CMC for any kind of observations on which independence is defined
via an arbitrary submodular information measure. Recently, this has been
discussed for observations in terms of binary strings where information is
understood in the sense of Kolmogorov complexity. Our approach enables us to
find computable alternatives to Kolmogorov complexity, e.g., the length of a
text after applying existing data compression schemes. We show that our CMC is
justified if one restricts the attention to a class of causal mechanisms that
is adapted to the respective information measure. Our justification is similar
to deriving the statistical CMC from functional models of causality, where
every variable is a deterministic function of its observed causes and an
unobserved noise term.
  Our experiments on real data demonstrate the performance of compression based
causal inference.
