Here's one approach. It assumes

1. Your array values don't contain '|'.
2. That the smaller array is a proper subset of the larger.

   If this is not the case it is a simple modification to add any elements from the smaller that do not appear in the larger...if that is your requirement.

3. That you don't need the resultant set in any specific order.

   Again, it's a relatively trivial modification if you do need to retain the input order, though it raises a conflict with the resolution of 2) above.

#! perl -slw
use strict;
use Data::Dumper;

sub diffAoA{
    my( $p, $q ) = @_;
    ( $p, $q ) = ( $q, $p ) if @$p < @$q;
    my %lookup = map{ join( '|', @$_ ), undef } @$p;
    delete @lookup{ map{ join( '|', @$_ ) } @$q };
    return map{ [ split '\|' ] } keys %lookup;
}

my @A0A1 = (
    [2003,1],[2003,3],[2003,4],[2004,1]
);

my @A0A2 = (
    [2003,1],[2003,2],[2003,3],[2003,4],[2003,5],[2003,6],
    [2003,7],[2003,8],[2003,9],[2003,10],[2003,11],[2003,12],
    [2004,1],[2004,2]
);

my @diff = diffAoA \@A0A1, \@A0A2;

print Dumper \@diff;

__END__
P:\test>test3
$VAR1 = [
          [ '2004',  '2' ],
          [ '2003', '12' ],
          [ '2003',  '5' ],
          [ '2003',  '2' ],
          [ '2003',  '9' ],
          [ '2003',  '8' ],
          [ '2003', '11' ],
          [ '2003',  '7' ],
          [ '2003', '10' ],
          [ '2003',  '6' ]
        ];
[download]