Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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).
share|cite|improve this question

migrated from Jan 2 '13 at 3:06

This question came from our site for theoretical computer scientists and researchers in related fields.

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."

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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