×

Modeling time criticality of information. (English) Zbl 1285.94021

Summary: 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.

MSC:

94A15 Information theory (general)
94A17 Measures of information, entropy
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gaži, P.; Rovan, B., Assisted problem solving and decompositions of finite automata, (Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEMʼ08 (2008), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 292-303 · Zbl 1133.68072
[2] Steskal, L., On usefulness of information: a computational approach (2010), Comenius University, Ph.D. thesis
[3] Labath, P.; Rovan, B., Simplifying DPDA using supplementary information, (Proceedings of the 5th International Conference on Language and Automata Theory and Applications, LATAʼ11 (2011), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 342-353 · Zbl 1330.68165
[4] Shannon, C. E., A mathematical theory of communication, Bell Syst. Tech. J., 27, 379-423 (1948), 623-656 · Zbl 1154.94303
[5] Calude, C. S., Information and Randomness: An Algorithmic Perspective (2010), Springer Publishing Company, Incorporated
[6] Even, S.; Selman, A. L.; Yacobi, Y., The complexity of promise problems with applications to public-key cryptography, Inf. Control, 61, 159-173 (1984) · Zbl 0592.94012
[7] Borodin, A.; El-Yaniv, R., Online Computation and Competitive Analysis (1998), Cambridge University Press: Cambridge University Press New York, NY, USA · Zbl 0931.68015
[8] Böckenhauer, H.-J.; Komm, D.; Královič, R.; Královič, R.; Mömke, T., On the advice complexity of online problems, (Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC ʼ09 (2009), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 331-340 · Zbl 1272.68466
[9] Hopcroft, J. E.; Motwani, R.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Series in Computer Science (2001), Addison-Wesley-Longman · Zbl 0980.68066
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.