A few links for the last item (TRAVESTY). As the source code in the 1st link shows, generation is indeed character-based, as suggested by the examples in the 2nd link.
Not your direct question, but it does seem to be musical composition on a computer using Markov chains earlier than your first in 63
An Experiment in Musical Composition (1957) DOI:10.1109/TEC.1957.5222016
"Several analyses of the sample and syntheses of new hymn melodies were performed with a large-scale computer. The machine has random-access storage of 230 sixteen-decimal digit numbers and separate magnetic drum storage of 4000 numbers and 10,000 instructions. It is synchronous in operation with most instructions requiring 1.3u sec"
3 comments
[ 3.0 ms ] story [ 21.6 ms ] threadhttp://wg20.criticalcodestudies.com/index.php?p=/discussion/...
https://languagehat.com/travesty/
https://elmcip.net/creative-work/travesty
https://www.amazon.com/Sentences-American-Poetry-Charles-Har...
An Experiment in Musical Composition (1957) DOI:10.1109/TEC.1957.5222016
"Several analyses of the sample and syntheses of new hymn melodies were performed with a large-scale computer. The machine has random-access storage of 230 sixteen-decimal digit numbers and separate magnetic drum storage of 4000 numbers and 10,000 instructions. It is synchronous in operation with most instructions requiring 1.3u sec"