Uniform one-dimensional fragments with one equivalence relation

DOI10.4230/LIPICS.CSL.2015.597MaRDI QIDQ5351985zbMATH OpenOpenAlexFDO

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

(10)

• Uniformization problem for variants of first order logic over finite words
• Alternating quantifiers in uniform one-dimensional fragments with an excursion into three-variable logic
• An excursion to the border of decidability: between two- and three-variable logic
• 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
• A uniform one-dimensional fragment with alternation of quantifiers

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)