I have a background in computer architecture and only cursory understanding of process networks. For a paper I am writing I need to understand prefix monotonicity properly.

For now I have "a stream transformer is prefix monotonic if its output for a given input record r is dependent only on the input stream up to and including r, and independent from whether r is the last record in the stream". But this was gathered by word-of-mouth and I am not sure it is the proper approach.

I would welcome suggestions for:

  • proper formal background and definitions;
  • useful analogies to explain the concept to a newcomer (the audience of the paper needs to understand prefix monotonicity but may not be knowledgeable with TCS).

This publication provides a definition of prefix monotonicity: link


"Prefix monotonicity reflects a basic property of communicating systems: assume we have observed a finite sequence of output messages for a corresponding finite sequence of input messages. Then if we observe additional input (thus the old input sequence is a prefix of the extended one) we may just observe additional output (thus the old output sequence is a prefix of the extended one). Prefix monotonicity provides a notion of causality between input and output. It reflects the stepwise consumption of input and production of output and guarantees the existence of least fixed points, which is mandatory for giving meaning to communication feedback loops."

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.