We delimit the boundary between decidability versus undecidability of
the weak monadic second-order logic of one successor (WS1S) extended
with linear cardinality constraints of the form 
  |X_1| + ... + |X_r| < |Y_1| + ... + |Y_s|, 
where the X is and Y js range over finite subsets of natural
numbers. Our decidability and undecidability results are based on an
extension of the classic logic-automata connection using a novel
automaton model based on Parikh maps.