Canonization for two variables and puzzles on the square

DOI10.1016/S0168-0072(96)00047-4zbMath0874.03039OpenAlexW2025727720MaRDI QIDQ1361251

Martin Otto

Publication date: 10 September 1997

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0168-0072(96)00047-4

zbMATH Keywords

infinitary logicfinite model theorydescriptive complexitycounting quantifiersfinite relational structurespolynomial time computable functorsPTIME Boolean queriesPTIME canonizationPTIME invariantsPTIME inverses

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other infinitary logic (03C75)

Related Items

Super/rosy \(L^k\)-theories and classes of finite structures ⋮ Graphs Identified by Logics with Counting ⋮ Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Upper and lower bounds for first order expressibility
• Infinitary logics and 0-1 laws
• An optimal lower bound on the number of variables for graph identification
• Structure and complexity of relational queries
• Infinitary logic and inductive definability over finite structures
• Relational queries computable in polynomial time
• Random Graph Isomorphism
• On languages with two variables
• On Moschovakis closure ordinals
• Deux ou trois choses que je sais de L_n
• The expressive power of fixed-point logic with counting
• On finite rigid structures
• The classical decision problem.