On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity

DOI10.1007/11591191_22zbMath1143.03331MaRDI QIDQ5387847

Wiesław Szwast, Lidia Tendera

Publication date: 27 May 2008

Published in: Logic for Programming, Artificial Intelligence, and Reasoning (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11591191_22

zbMATH Keywords

computational complexity; transitivity; guarded fragment; decision problem; finite model

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03B25: Decidability of theories and sets of sentences

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

03C13: Model theory of finite structures

03B20: Subsystems of classical logic (including intuitionistic logic)

Related Items

Complexity of hybrid logics over transitive frames, On the complexity of the two-variable guarded fragment with transitive guards, The guarded fragment with transitive guards