Uniform one-dimensional fragments with one equivalence relation

DOI10.4230/LIPICS.CSL.2015.597zbMATH Open1373.03012OpenAlexW2292490089MaRDI QIDQ5351985FDOQ5351985

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

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

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)

Cited In (7)

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

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)