Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps (Q4635882)

From MaRDI portal
scientific article; zbMATH DE number 6863496
Language Label Description Also known as
English
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
scientific article; zbMATH DE number 6863496

    Statements

    Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps (English)
    0 references
    0 references
    0 references
    23 April 2018
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    first-order logic
    0 references
    Weisfeiler-Leman algorithm
    0 references
    XORification
    0 references
    bounded-variable fragment
    0 references
    first-order counting logic
    0 references
    hardness condensation
    0 references
    lower bounds
    0 references
    quantifier depth
    0 references
    refinement iterations
    0 references
    trade-offs
    0 references
    0 references
    0 references