Knowledge = Observation + Memory + Computation

详细信息    查看全文

• 作者：Blaise Genest (14)
  Doron Peled (15)
  Sven Schewe (16)
  
  14. CNRS ; IRISA ; Rennes ; France
  15. Bar Ilan University ; Ramat Gan ; Israel
  16. University of Liverpool ; Liverpool ; UK
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9034
• 期：1
• 页码：215-229
• 全文大小：278 KB
• 参考文献：1. Basu, A., Bensalem, S., Peled, D., Sifakis, J. (2011) Priority scheduling of distributed systems based on model checking. Formal Methods in System Design 39: pp. 229-245 CrossRef
  2. Diekert, V., Rozenberg, G.: In particular. In: Diekert, V., Muscholl, A. (eds.) The Book of Traces, ch.聽8, World Scientific, Singapore (1995)
  3. Fagin, R., Halpern, J.Y., Moses, Y., Vardi, M. (1995) Reasoning About Knowledge. MIT Press, Cambridge
  4. Gastin, P., Lerman, B., Zeitoun, M. Distributed Games with Causal Memory Are Decidable for Series-Parallel Systems. In: Lodaya, K., Mahajan, M. eds. (2004) FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science. Springer, Heidelberg, pp. 275-286 CrossRef
  5. Genest, B., Gimbert, H., Muscholl, A., Walukiewicz, I.: Optimal zielonka-type construction of deterministic asynchronous automata. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part II. LNCS, vol.聽6199, pp. 52鈥?3. Springer, Heidelberg (2010)
  6. Genest, B., Gimbert, H., Muscholl, A., Walukiewicz, I. Asynchronous Games over Tree Architectures. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. eds. (2013) Automata, Languages, and Programming. Springer, Heidelberg, pp. 275-286 CrossRef
  7. Genest, B., Muscholl, A.: Constructing Exponential-size Deterministic Zielonka Automata. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006, Part II. LNCS, vol.聽4052, pp. 565鈥?76. Springer, Heidelberg (2006)
  8. Graf, S., Peled, D., Quinton, S. Monitoring Distributed Systems Using Knowledge. In: Bruni, R., Dingel, J. eds. (2011) Formal Techniques for Distributed Systems. Springer, Heidelberg, pp. 183-197 CrossRef
  9. Krishnan, R., Venkatesh, S.: Optimizing the gossip automaton, Report TCS-94-3, School of Mathematics, SPIC Science Foundation, Madras, India (1994)
  10. Mazurkiewicz, A.: Concurrent program schemes and their interpretation. Technical report, DAIMI Report PB-78, Aarhus University (1977)
  11. Meyden, R. (1998) Common Knowledge and Update in Finite Environment. Information and Computation 140: pp. 115-157 CrossRef
  12. Meyden, R., Shilov, N.V. Model Checking Knowledge and Time in Systems with Perfect Recall. In: Pandu Rangan, C., Raman, V., Sarukkai, S. eds. (1999) Foundations of Software Technology and Theoretical Computer Science. Springer, Heidelberg, pp. 432-445 CrossRef
  13. Meyer, A.R., Stockmeyer, L.J.: The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space. In: Proc. of STOC 1973, pp. 1鈥? (1973)
  14. Mukund, M., Sohoni, M. (1997) Keeping Track of the Latest Gossip in a Distributed System. Distr. Computing 10: pp. 137-148 CrossRef
  15. Madhusudan, P., Thiagarajan, P.S., Yang, S. The MSO Theory of Connectedly Communicating Processes. In: Sarukkai, S., Sen, S. eds. (2005) FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science. Springer, Heidelberg, pp. 201-212 16" target="_blank" title="It opens in new window">CrossRef
  16. Ricker, S.L., Rudie, K. (2000) Know means no: Incorporating knowledge into discrete-event control systems. IEEE Trans. Automat. Contr. 45: pp. 1656-1668 16" target="_blank" title="It opens in new window">CrossRef
  17. Zielonka, W. (1987) Notes on finite asynchronous automata. R.A.I.R.O. - Informatique Th茅orique et Applications 21: pp. 99-135
  
• 作者单位：Foundations of Software Science and Computation Structures
• 丛书名：978-3-662-46677-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

We compare three notions of knowledge in concurrent system: memoryless knowledge, knowledge of perfect recall, and causal knowledge. Memoryless knowledge is based only on the current state of a process, knowledge of perfect recall can take into account the local history of a process, and causal knowledge depends on the causal past of a process, which comprises the information a process can obtain when all processes exchange the information they have when performing joint transitions. We compare these notions in terms of knowledge strength, number of bits required to store this information, and the complexity of checking if a given process has a given knowledge. We show that all three notions of knowledge can be implemented using finite memory. Causal knowledge proves to be strictly more powerful than knowledge with perfect recall, which in turn proves to be strictly more powerful than memoryless knowledge. We show that keeping track of causal knowledge is cheaper than keeping track of knowledge of perfect recall.