On the uniform one-dimensional fragment

2016/04/06 by Kuusisto, Antti
#Artificial Intelligence (cs.AI) #F.4.1 #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1604.01673

Abstract

The uniform one-dimensional fragment of first-order logic, U1, is a formalism that extends two-variable logic in a natural way to contexts with relations of all arities. We survey properties of U1 and investigate its relationship to description logics designed to accommodate higher arity relations, with particular attention given to DLR_reg. We also define a description logic version of a variant of U1 and prove a range of new results concerning the expressivity of U1 and related logics.

Related

• One-dimensional fragment of first-order logic
• Complexity and Expressivity of Uniform One-Dimensional Fragment with Equality
• Uniform One-Dimensional Fragment over Ordered Structures
• Uniform Guarded Fragments
• Towards a Model Theory of Ordered Logics: Expressivity and Interpolation (Extended version)