2021/04/17 by Mikhail Rybakov, Dmitry Shkatov
Computer Science · Mathematics · Medicine · #Advanced Algebra and Logic #Combinatorics #Computer science #Discrete mathematics #Mathematics #Modal #Order (exchange) #Physics #Platelet Disorders and Treatments #Predicate (mathematical logic) #Recursively enumerable language #Sigma #cs.LO #semigroups and automata theory
paper · pdf · doi:10.1093/logcom/exab030
openalex created_date 2020/09/01 · openalex publication_date 2021/04/17 · arxiv created 2021/05/25 · arxiv updated 2021/05/26 · openalex updated_date 2026/08/05
Abstract We study the algorithmic properties of first-order monomodal logics of frames ⟨ \textrmI \textrmN, \leqslant ⟩ , ⟨ \textrmI \textrmN, < ⟩ , ⟨ \mathbb Q, \leqslant ⟩ , ⟨ \mathbb Q, < ⟩ , ⟨ \textrmI \textrmR, \leqslant ⟩ , ⟨ \textrmI \textrmR, < ⟩ , as well as some related logics, in languages with restrictions on the number of individual variables as well as the number and arity of predicate letters. We show that the logics of frames based on \textrmI \textrmN are \varPi 11-hard—thus, not recursively enumerable—in languages with two individual variables, one monadic predicate letter and one proposition letter. We also show that the logics of frames based on \mathbb Q and \textrmI \textrmR are \varSigma 01-hard in languages with the same restrictions. Similar results are obtained for a number of related logics.