dpkg -L w3c-markup-validator
lista todos os arquivos no pacote. Você quer os executáveis no caminho, então
dpkg -L w3c-markup-validator | grep /bin/
fornecerá uma boa aproximação. Se você quer ser realmente preciso, aqui está um regexp que irá reter apenas os arquivos nos diretórios em seu $PATH
.
dpkg -L bash | grep -E "^${PATH//:/\/|^}\$"