This is more a theoretical question about the overall solvability of the problem with scripting, dependencies and ordering. All inputs to a script come via a transaction, so, I am asking if there were a set of dependencies specifiable in any given transaction that forced the referenced transactions* to be ordered before the new transaction, is this enough for the system to decide on an overall order?
*) To address your other point, specifically in ethereum, dependencies would have to be specified as references to previous blocks, not previous transactions because, as you point out, there is only a partial order in a blockchain. The system would then have to group transactions with compatible dependencies into blocks.
In addition, yes, I am hoping an
eventual total ordering of transactions is possible.