I didn't like any of the solutions so far since none of them handle input in the same format as their own output.

#!/usr/bin/perl -w
use strict;
sub RunLengthEncode {
    my @out;
    while(  @_  ) {
        my $next= shift;
        if(  ! ref($next)  ) {
            $next= {count=>1,value=>$next};
        }
        if(  @out  &&  $out[$#out]{value} eq $next->{value}  ) {
            $out[$#out]{count} += $next->{count};
        } else {
            push @out, $next;
        }
    }
    return @out;
}
for(  @ARGV  ) {
    print join ",", map { $_->{count}."*".$_->{value} }
        RunLengthEncode( split /,/, $_ );
    print $/;
}
[download]

But that doesn't define a bunch of rules for "reducing" a problem because, well, it wasn't written in Prolog. (:

        - tye (but my friends call me "Tye")