Hmmm, seems more like a constrained variation of Longest common substring problem. Confusion probably due to looseness of my description.

I agree that the combined files aren't guaranteed to represent the true sequence of commands. The example you provided is one case of aliasing that demonstrates this. Even more problematic is that multiple interactive shells will write to the same history file on exit.

The dates of all the commands in the history file are not known, only the upper bound. The file is a rolling window of the entered commands. If fewer commands are entered than the hist file size, the oldest commands are are eliminated from the file.