Uniform one-dimensional fragments with one equivalence relation

DOI10.4230/LIPICS.CSL.2015.597MaRDI QIDQ5351985zbMATHOpenAlexFDO

Authors Emanuel Kieroński, Antti Kuusisto

Publication date 31 August 2017

Full work available at URL https://dblp.uni-trier.de/db/conf/csl/csl2015.html#KieronskiK15

zbMATH Keywords

complexityexpressivityequivalence relationstwo-variable logicuniform one-dimensional fragments

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Subsystems of classical logic (including intuitionistic logic) (03B20) Descriptive complexity and finite models (68Q19)

Recommendations

• Complexity and expressivity of uniform one-dimensional fragment with equality
• One-dimensional logic over words
• One-dimensional fragment of first-order logic
• Unary negation fragment with equivalence relations has the finite model property
• One-Dimensional Logic over Trees

Cited in

(7)

• One-Dimensional Logic over Trees
• Uniform guarded fragments
• One-dimensional fragment of first-order logic
• Unary negation fragment with equivalence relations has the finite model property
• Complexity and expressivity of uniform one-dimensional fragment with equality
• Uniformization problem for variants of first order logic over finite words
• One-dimensional logic over words

This page was built for publication: Uniform one-dimensional fragments with one equivalence relation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5351985)