2014/07/15 by Arthur Milchior, Milchior, Arthur
Computer Science · #Advanced Algebra and Logic #FOS: Computer and information sciences #Formal Methods in Verification #Logic in Computer Science (cs.LO) #cs.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1407.4032
arxiv created 2014/07/15 · openalex publication_date 2014/07/15 · arxiv updated 2014/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that descriptive complexity's result extends in High Order Logic to capture the expressivity of Turing Machine which have a finite number of alternation and whose time or space is bounded by a finite tower of exponential. Hence we have a logical characterisation of ELEMENTARY. We also consider the expressivity of some fixed point operators and of monadic high order logic. Finally, we show that Variable Order logic over finite structures contain the Analytical Hierarchy.