

Symposium on logic and computability "Logic and Computation Day"
June 7, 2013 16:15–17:00, Moscow, Steklov Mathematical Institute of RAS






Hamming metric and products of modal logics
I. B. Shapirovskii^{} ^{} A. A. Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow

Number of views: 
This page:  47 

Abstract:
With a set S of words in an alphabet A we associate the frame (S,H), where sHt iff s and t are words of the same length and h(s,t) = 1 for the Hamming distance h, and investigate unimodal logics of such frames. These logics are closely related to manydimensional modal logics: if we consider the nth power of the inequality frame over a given alphabet A, then the Hamming boxoperator on words of length n acts as the conjunction of all boxoperators of the product; on the other hand, we show that all modalities of the logic of the nth power of A with the universal relation can be expressed in the unimodal language with the Hamming boxoperator. We present results on (un)decidability, complexity, (non)finite axiomatizability, and completeness for these logics. Joint work with Andrey Kudinov and Valentin Shehtman.
Language: English

