What'd be the problem with a package "coreutils-acl" that just Conflicts: and Provides: coreutils?
I'd worry about the fragility of such a system in the face of upgrades,
the inability for a coreutils-acl to do a versioned provides: of
coreutils (meaning people would need to depend on some version of
coreutils|coreutils-acl), and the difficulty in removing such a package
in the future.
Mike Stone
