Modeling time criticality of information

• We present a formal setting for time criticality of information in computations.
• We propose a measure of usefulness of advice.
• Time criticality exhibits a complex and unexpected behavior during a computation.

In this paper, we continue the research on formal treatment of attributes of information, based on the computational approach. In this scenario, the usefulness of advisory information is measured by the decrease in complexity of a problem we need to solve. We propose to model the time criticality via usefulness of a piece of information which is received during the computation. As a modeling tool, we use deterministic finite automata.We give two definitions of time criticality. In the static case, we consider supplementary information which concerns the entire input instance. In the dynamic case, we consider information about the unprocessed part of the input. Despite the simplicity of our model, we shall see that the development of time criticality may exhibit an interesting behavior.