5.01.2006

Concurrent Secrets

Rozważamy następujący problem: dany jest automat, dany jest zbiór obserwatorów, każdy z obserwatorów dysponuje częściowymi obserwacjami przebiegu zdarzeń (podalfabet całego alfabetu), dla każdego obserwatora ustalono język sekretów (regularny). Interesuje nas zapewnienie, by obserwatorzy NIE MOGLI nabrać pewności co do prawdziwego przebiegu zdarzeń. Pokazujemy, ze (1) istnieje maksymalny podjęzyk zapewniający sekretność, (2) na ogół nie jest on regularny, (3) w pewnych, rozsądnych, przypadkach potrafimy pokazać, ze maksymalny język jest regularny, w innych podobnych przypadkach pytanie jest wciąż otwarte.
Badania powyższe są prowadzone we współpracy z zespołem w IRISA, Rennes, Francja.