Pith. sign in

REVIEW 2 major objections 2 minor 50 references

Computation and Size of Interpolants for Hybrid Modal Logics

T0 review · 2 major / 2 minor · reviewed 2026-05-21 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Craig interpolants for many hybrid modal logics can be computed in fourfold exponential time when they exist via hypermosaic elimination.

desk verdict The paper gives a constructive 4-EXPTIME procedure for Craig interpolants in hybrid modal logics via a new hypermosaic elimination technique, plus an undecidability result for uniform interpolants. read the letter →

arxiv 2602.15821 v2 pith:3MLYHHBS submitted 2026-02-17 cs.LO

Jean Christoph Jung , Jędrzej Ko{l}odziejski , Frank Wolter This is my paper · ORCID
classification cs.LO
keywords Craiginterpolationhybridmodallogichypermosaiceliminationinterpolantcomputationuniforminterpolantsundecidabilitydescription
checked against reality_from_one_distinctionCost.FunctionalEquation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Hybrid modal logics include nominals that allow naming worlds, yet they fail the Craig Interpolation Property. This paper develops a hypermosaic elimination technique that constructs interpolants by successively removing inconsistent mosaic combinations while preserving satisfiability in the hybrid language. The resulting procedure runs in fourfold exponential time for standard variants such as those with nominals and the down-arrow operator. The same analysis shows that deciding whether a uniform interpolant exists is undecidable, in contrast to ordinary modal and intuitionistic logics. These results matter because interpolants can act as explicit descriptions or as separators between positive and negative examples inside description-logic knowledge bases.

What carries the argument

hypermosaic elimination technique that removes inconsistent mosaics while tracking nominal constraints and hybrid accessibility relations to produce an interpolant of controlled size.

What would settle it

An explicit hybrid modal formula pair that possesses an interpolant yet requires more than fourfold exponential time under any correct hypermosaic procedure, or a hybrid logic in which uniform interpolant existence is decidable.

Watch

Extended reading notes

Core claim

Using a hypermosaic elimination technique, Craig interpolants in many standard hybrid modal logics can be computed in fourfold exponential time if they exist. The existence of uniform interpolants is undecidable.

Load-bearing premise

The hypermosaic elimination procedure works without further restrictions on the hybrid modal logics beyond the presence of nominals and standard modal operators.

Editorial extensions

If this is right

  • Interpolants become algorithmically obtainable in 4EXPTIME for all hybrid logics covered by the technique.
  • Uniform interpolants cannot be decided for existence, unlike the situation in modal or intuitionistic logic.
  • Interpolants serve directly as definite descriptions or data separators in description-logic applications.
  • The method supplies an explicit size bound on the interpolants that are produced.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same elimination idea might be adapted to other logics that lack the Craig Interpolation Property once suitable mosaic representations are identified.
  • Undecidability of uniform interpolants suggests a fundamental trade-off between expressive power and the ability to compute uniform interpolants in hybrid settings.
  • Restricted fragments, for example those with bounded modal depth, could restore decidability of uniform interpolants while retaining most hybrid features.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The paper introduces a hypermosaic elimination technique to compute Craig interpolants for many standard hybrid modal logics (with nominals) in fourfold exponential time when they exist. It also proves that the existence of uniform interpolants is undecidable in these logics, contrasting with modal and intuitionistic logics.

Significance. If the hypermosaic construction is correct, the result supplies the first explicit complexity bound and constructive method for interpolant computation in a class of logics without the Craig interpolation property. This is relevant for applications in description logics where interpolants serve as definite descriptions or data separators. The undecidability result for uniform interpolants is a clear negative result that sharpens the boundary between hybrid and non-hybrid modal logics.

major comments (2)
  1. [§4] §4 (Hypermosaic elimination procedure): The rules for propagating and eliminating nominal constraints across mosaics must be shown to preserve global uniqueness and consistency of nominal interpretations. The skeptic concern is valid here: if a nominal can be assigned to different worlds in merged mosaics without an explicit global consistency check, the output formula may satisfy local modal conditions yet fail to be a valid interpolant for formulas containing nominals. This is load-bearing for the central 4-EXPTIME claim.
  2. [Theorem 5.1] Theorem 5.1 (or the main complexity theorem): The fourfold exponential bound is derived from the size of the hypermosaic space; the proof sketch must explicitly count the number of possible nominal assignments and confirm that the elimination phase does not introduce an extra exponential factor when enforcing rigidity of nominals.
minor comments (2)
  1. [Abstract] The abstract and introduction should list the precise hybrid modal logics covered (e.g., whether the result holds for all extensions with the universal modality or only for the basic hybrid logic K with nominals).
  2. [§3] Notation for mosaics and hypermosaics should be introduced with a small illustrative example early in §3 to clarify how nominals differ from ordinary propositional variables in the construction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. The points raised concern the exposition of correctness and complexity details in the hypermosaic technique. We respond to each major comment below and will incorporate clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: [§4] §4 (Hypermosaic elimination procedure): The rules for propagating and eliminating nominal constraints across mosaics must be shown to preserve global uniqueness and consistency of nominal interpretations. The skeptic concern is valid here: if a nominal can be assigned to different worlds in merged mosaics without an explicit global consistency check, the output formula may satisfy local modal conditions yet fail to be a valid interpolant for formulas containing nominals. This is load-bearing for the central 4-EXPTIME claim.

    Authors: We agree that explicit preservation of global uniqueness and consistency for nominals is essential. The hypermosaic construction maintains a single global nominal-to-world map that is updated during each merge and elimination step; local constraints are only applied if they are compatible with this map. To address the concern directly, we will insert a new lemma (Lemma 4.7) in §4 that proves, by induction on the elimination sequence, that every intermediate hypermosaic preserves a rigid, globally unique interpretation for all nominals appearing in the input formulas. The proof will also show that any interpolant extracted from a final consistent hypermosaic satisfies the original formulas under this global assignment. revision: yes

  2. Referee: [Theorem 5.1] Theorem 5.1 (or the main complexity theorem): The fourfold exponential bound is derived from the size of the hypermosaic space; the proof sketch must explicitly count the number of possible nominal assignments and confirm that the elimination phase does not introduce an extra exponential factor when enforcing rigidity of nominals.

    Authors: The size of the hypermosaic space is bounded by the product of the number of possible modal types (already 3-EXPTIME) and the number of functions assigning the k nominals (k linear in the input size) to the at most exponentially many worlds per mosaic. This yields an additional single-exponential factor, keeping the overall bound at 4-EXPTIME. The elimination phase itself performs only local consistency checks and map updates that are polynomial in the representation size of each hypermosaic; no re-enumeration of assignments occurs. We will expand the proof of Theorem 5.1 with an explicit counting paragraph and a separate lemma bounding the time for rigidity enforcement. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: novel elimination technique yields independent complexity bound

full rationale

The paper establishes a 4-EXPTIME procedure for Craig interpolants via a new hypermosaic elimination technique applied to standard hybrid modal semantics with nominals. No quoted definitions, equations, or self-citations reduce the claimed existence, size, or complexity result to fitted inputs or prior results by construction. The derivation is self-contained against external modal logic benchmarks, with the undecidability of uniform interpolants likewise resting on a separate reduction that does not loop back to the interpolant computation claim.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The central claims rest on the correctness of the new hypermosaic elimination procedure and on standard background properties of hybrid modal logics with nominals.

assumptions (1)
  • domain assumption Hybrid modal logics are defined with nominals and standard modal semantics
    Invoked throughout as the setting for which the technique and undecidability hold.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computation and Size of Interpolants for Hybrid Modal Logics." pith.science (2026). https://pith.science/paper/3MLYHHBS

@misc{pith2026260215821,
  author       = {Pith},
  title        = {Pith review of: Computation and Size of Interpolants for Hybrid Modal Logics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3MLYHHBS}},
  note         = {Machine review of arXiv:2602.15821}
}
read the original abstract

Recent research has established complexity results for the problem of deciding the existence of interpolants in logics lacking the Craig Interpolation Property (CIP). The proof techniques developed so far are non-constructive, and no meaningful bounds on the size of interpolants are known. Hybrid modal logics (or modal logics with nominals) are a particularly interesting class of logics without CIP: in their case, CIP cannot be restored without sacrificing decidability and, in applications, interpolants in these logics can serve as definite descriptions and separators between positive and negative data examples in description logic knowledge bases. In this contribution we show, using a new hypermosaic elimination technique, that in many standard hybrid modal logics Craig interpolants can be computed in fourfold exponential time, if they exist. On the other hand, we show that the existence of uniform interpolants is undecidable, which is in stark contrast to modal or intuitionistic logic where uniform interpolants always exist.

Discussion (0). Continue with ORCID to comment.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    We extend the elimination method further by eliminating unrealizable sets of mosaics, called hypermosaics... Theorem 12. For a hypermosaic H, the following are equivalent: H is realizable by an H(σ)-bisimulation; H ∈ Z∗.

  • IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    The construction of separators proceeds by induction on the number of rounds of the elimination procedure... sep_i(c, t) defined via Sepc-star-types and case distinctions on nominal types.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

50 extracted references · 50 canonical work pages

  1. [1]

    Interpolation and model checking,

    K. L. McMillan, “Interpolation and model checking,” inHandbook of Model Checking, E. M. Clarke, T. A. Henzinger, H. Veith, and R. Bloem, Eds. Springer, 2018, pp. 421–446. [Online]. Available: https://doi.org/10.1007/978-3-319-10575-8_14

    work page doi:10.1007/978-3-319-10575-8_14 2018

  2. [2]

    Benedikt, J

    M. Benedikt, J. Leblay, B. ten Cate, and E. Tsamoura,Generating Plans from Proofs: The Interpolation-based Approach to Query Reformulation, ser. Synthesis Lectures on Data Management. Morgan & Claypool Pub- lishers, 2016

    work page 2016

  3. [3]

    Projective beth definability and craig interpolation for relational query optimization (material to accompany invited talk),

    D. Toman and G. E. Wedell, “Projective beth definability and craig interpolation for relational query optimization (material to accompany invited talk),” inProceedings of the Second Workshop on Second-Order Quantifier Elimination and Related Topics (SOQE 2021) associated with the 18th International Conference on Principles of Knowledge Representation and ...

    work page 2021

  4. [4]

    Logical separability of labeled data examples under ontologies,

    J. C. Jung, C. Lutz, H. Pulcini, and F. Wolter, “Logical separability of labeled data examples under ontologies,”Artif. Intell., vol. 313, p. 103785,

    work page

  5. [5]

    Available: https://doi.org/10.1016/j.artint.2022.103785

    [Online]. Available: https://doi.org/10.1016/j.artint.2022.103785

    work page doi:10.1016/j.artint.2022.103785 2022

  6. [6]

    Universal proof theory: Semi-analytic rules and craig interpolation,

    A. A. Tabatabai and R. Jalali, “Universal proof theory: Semi-analytic rules and craig interpolation,”Ann. Pure Appl. Log., vol. 176, no. 1, p. 103509,

    work page

  7. [7]

    Available: https://doi.org/10.1016/j.apal.2024.103509

    [Online]. Available: https://doi.org/10.1016/j.apal.2024.103509

    work page doi:10.1016/j.apal.2024.103509 2024

  8. [8]

    Fitting, R

    M. Fitting and R. Kuznets, “Modal interpolation via nested sequents,” Ann. Pure Appl. Log., vol. 166, no. 3, pp. 274–305, 2015. [Online]. Available: https://doi.org/10.1016/j.apal.2014.11.002

    work page doi:10.1016/j.apal.2014.11.002 2015

Show all 50 references
  1. [9]

    Beth definability in expressive description logics,

    B. ten Cate, E. Franconi, and I. Seylan, “Beth definability in expressive description logics,”J. Artif. Intell. Res., vol. 48, pp. 347–414, 2013

    2013

  2. [10]

    Interpolation for extended modal languages,

    B. ten Cate, “Interpolation for extended modal languages,”J. Symb. Log., vol. 70, no. 1, pp. 223–234, 2005

    2005

  3. [11]

    Interpolation in knowledge rep- resentation,

    J. C. Jung, P. Koopmann, and M. Knorr, “Interpolation in knowledge rep- resentation,”arXiv preprint arXiv:2512.08833, 2025

    2025

  4. [12]

    Formal properties of modularisation,

    B. Konev, C. Lutz, D. Walther, and F. Wolter, “Formal properties of modularisation,” inModular Ontologies: Concepts, Theories and Techniques for Knowledge Modularization, ser. Lecture Notes in Computer Science, H. Stuckenschmidt, C. Parent, and S. Spaccapietra, 30 Eds. Springe...

    2009 doi

  5. [13]

    Decomposing de- scription logic ontologies,

    B. Konev, C. Lutz, D. K. Ponomaryov, and F. Wolter, “Decomposing de- scription logic ontologies,” inProceedings of the 12th International Confer- ence on Principles of Knowledge Representation and Reasoning, KR 2010. AAAI Press, 2010

    2010

  6. [14]

    Living without beth and craig: Definitions and interpolants in description and modal logics with nominals and role inclusions,

    A. Artale, J. C. Jung, A. Mazzullo, A. Ozaki, and F. Wolter, “Living without beth and craig: Definitions and interpolants in description and modal logics with nominals and role inclusions,”ACM Trans. Comput. Log., vol. 24, no. 4, pp. 34:1–34:51, 2023. [Online]. Available: http...

    2023 doi

  7. [15]

    An investigation of definability in ontology alignment,

    D. Geleta, T. R. Payne, and V. Tamma, “An investigation of definability in ontology alignment,” inKnowledge Engineering and Knowledge Management - 20th International Conference, EKAW 2016, Bologna, Italy, November 19-23, 2016, Proceedings, ser. Lecture Notes in Computer Scienc...

    2016 doi

  8. [16]

    On free description logics with definite descriptions,

    A. Artale, A. Mazzullo, A. Ozaki, and F. Wolter, “On free description logics with definite descriptions,” inProceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, 2021, pp. 63–73. [Online]. Available: https://doi.org/...

    2021 doi

  9. [17]

    Graded modal logic and counting bisimula- tion,

    M. Otto, “Graded modal logic and counting bisimula- tion,”CoRR, vol. abs/1910.00039, 2019. [Online]. Available: http://arxiv.org/abs/1910.00039

    1910

  10. [18]

    A note on graded modal logic,

    M. de Rijke, “A note on graded modal logic,”Stud Log- ica, vol. 64, no. 2, pp. 271–283, 2000. [Online]. Available: https://doi.org/10.1023/A:1005245900406

    2000 doi

  11. [19]

    A road-map on complexity for hybrid logics,

    C. Areces, P. Blackburn, and M. Marx, “A road-map on complexity for hybrid logics,” inProceedings of the 8th Annual Conference of the European Association for Computer Science Logic, CSL 1999. Springer, 1999, pp. 307–321. [Online]. Available: https://doi.org/10.1007/3-540-48168-0_22

    1999 doi

  12. [20]

    The complexity of reasoning with cardinality restrictions and nominals in expressive description logics,

    S. Tobies, “The complexity of reasoning with cardinality restrictions and nominals in expressive description logics,”J. Artif. Intell. Res., vol. 12, pp. 199–217, 2000. [Online]. Available: https://doi.org/10.1613/jair.705

    doi

  13. [21]

    Integrating description logics and action formalisms for reasoning about web services,

    F. Baader, M. Milicic, C. Lutz, U. Sattler, and F. Wolter, “Integrating description logics and action formalisms for reasoning about web services,” Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, Germany, LTCS-Report LTC...

    2005

  14. [22]

    Interpolation in modal logic,

    M. Marx, “Interpolation in modal logic,” inProceedings of the 7th International Conference on Algebraic Methodology and Software Technology, AMAST 1998. Springer, 1998, pp. 154–163. [Online]. Available: https://doi.org/10.1007/3-540-49253-4_13

    1998 doi

  15. [23]

    From interpolating formulas to separating languages and back again,

    A. Kurucz, F. Wolter, and M. Zakharyaschev, “From interpolating formulas to separating languages and back again,”CoRR, vol. abs/2508.12805,

  16. [24]

    Available: https://doi.org/10.48550/arXiv.2508.12805

    [Online]. Available: https://doi.org/10.48550/arXiv.2508.12805

    doi

  17. [25]

    Effective interpolation and preservation in guarded logics,

    M. Benedikt, B. ten Cate, and M. Vanden Boom, “Effective interpolation and preservation in guarded logics,”ACM Trans. Comput. Log., vol. 17, no. 2, pp. 8:1–8:46, 2016

    2016

  18. [26]

    Six proofs of interpolation for the modal logic k,

    N. Bezhanishvili, B. t. Cate, and R. Iemhoff, “Six proofs of interpolation for the modal logic k,”arXiv preprint arXiv:2510.16398, 2025

    2025

  19. [27]

    Living without beth and craig: Definitions and interpolants in the guarded and two-variable fragments,

    J. C. Jung and F. Wolter, “Living without beth and craig: Definitions and interpolants in the guarded and two-variable fragments,” in Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021. IEEE, 2021, pp. 1–14. [Online]. Available: https://d...

    2021 doi

  20. [28]

    Deciding the existence of interpolants and definitions in first-order modal logic,

    A. Kurucz, F. Wolter, and M. Zakharyaschev, “Deciding the existence of interpolants and definitions in first-order modal logic,”Log. Methods Comput. Sci., vol. 21, no. 4, 2025. [Online]. Available: https://doi.org/10.46298/lmcs-21(4:6)2025

    2025 doi

  21. [29]

    Computation of interpolants for description logic concepts in hard cases,

    J. C. Jung, J. Kołodziejski, and F. Wolter, “Computation of interpolants for description logic concepts in hard cases,” inProc. of DL 2025, 2025

    2025

  22. [30]

    FAME(Q): an automated tool for forgetting in description logics with qualified number restrictions,

    Y. Zhao and R. A. Schmidt, “FAME(Q): an automated tool for forgetting in description logics with qualified number restrictions,” inAutomated Deduction - CADE 27 - 27th International Conference on Automated Deduction, Natal, Brazil, August 27-30, 2019, Proceedings, ser. Lecture...

    2019 doi

  23. [31]

    LETHE:forgettinganduniforminterpolationforexpressive description logics,

    P.Koopmann, “LETHE:forgettinganduniforminterpolationforexpressive description logics,”Künstliche Intell., vol. 34, no. 3, pp. 381–387, 2020. [Online]. Available: https://doi.org/10.1007/s13218-020-00655-w

    2020 doi

  24. [32]

    On an interpretation of second order quantification in first order intuitionistic propositional logic,

    A. M. Pitts, “On an interpretation of second order quantification in first order intuitionistic propositional logic,”J. Symb. Log., vol. 57, no. 1, pp. 33–52, 1992. [Online]. Available: https://doi.org/10.2307/2275175

    1992 doi

  25. [33]

    Uniform interpolation and layered bisimulation,

    A. Visseret al., “Uniform interpolation and layered bisimulation,” in Gödel’96: Logical foundations of mathematics, computer science and physics—Kurt Gödel’s legacy. Association for Symbolic Logic, 1996, pp. 139–164. 32

    1996

  26. [34]

    Definitorially complete description logics,

    B. ten Cate, W. Conradie, M. Marx, and Y. Venema, “Definitorially complete description logics,” inProceedings of the 10th International Conference on Principles of Knowledge Representation and Reason- ing, KR 2006. AAAI Press, 2006, pp. 79–89. [Online]. Available: http://www.a...

    2006

  27. [35]

    Constructive interpolation in hybrid logic,

    P. Blackburn and M. Marx, “Constructive interpolation in hybrid logic,” J. Symb. Log., vol. 68, no. 2, pp. 463–480, 2003. [Online]. Available: https://doi.org/10.2178/jsl/1052669059

    2003 doi

  28. [36]

    Transfer results for hybrid logic. part I: the case without satisfaction operators,

    N. Bezhanishvili and B. ten Cate, “Transfer results for hybrid logic. part I: the case without satisfaction operators,”J. Log. Comput., vol. 16, no. 2, pp. 177–197, 2006. [Online]. Available: https://doi.org/10.1093/logcom/exi056

    2006 doi

  29. [37]

    Hybrid logics: Characterization, interpolation and complexity,

    C. Areces, P. Blackburn, and M. Marx, “Hybrid logics: Characterization, interpolation and complexity,”J. Symb. Log., vol. 66, no. 3, pp. 977–1010,

  30. [38]

    Available: https://doi.org/10.2307/2695090

    [Online]. Available: https://doi.org/10.2307/2695090

    doi

  31. [39]

    Hybrid logics,

    C. Areces and B. ten Cate, “Hybrid logics,” inHandbook of Modal Logic. Elsevier, 2007, vol. 3, pp. 821–868

    2007

  32. [40]

    The complexity of explicit definitions,

    H. Friedman, “The complexity of explicit definitions,”Advances in Mathematics, vol. 20, no. 1, pp. 18–29, 1976. [Online]. Available: https://www.sciencedirect.com/science/article/pii/0001870876901675

    1976

  33. [41]

    Baader, I

    F. Baader, I. Horrocks, C. Lutz, and U. Sattler,An Introduction to De- scription Logic. Cambridge University Press, 2017

    2017

  34. [42]

    Uniform interpolation, automata and the modalµ-calculus,

    G. D’Agostino and M. Hollenberg, “Uniform interpolation, automata and the modalµ-calculus,” inProceedings of the 1st Workshop on Advances in Modal Logic, AiML-1. CSLI Publications, 1996, pp. 73–84

    1996

  35. [43]

    Ebbinghaus and J

    H. Ebbinghaus and J. Flum,Finite model theory, ser. Perspectives in Math- ematical Logic. Springer, 1995

    1995

  36. [44]

    Baader, Diego

    Franz. Baader, Diego. Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F.. Patel-Schneider, Eds.,The Description Logic Handbook: The- ory, Implementation, and Applications. Cambridge University Press, 2003

    2003

  37. [45]

    The interpolant existence problem for weak K4 and difference logic,

    A. Kurucz, F. Wolter, and M. Zakharyaschev, “The interpolant existence problem for weak K4 and difference logic,” inAdvances in Modal Logic, AiML 2024, Prague, Czech Republic, August 19-23, 2024, A. Ciabattoni, D. Gabelaia, and I. Sedlár, Eds. College Publications, 2024, pp. 465–484

    2024

  38. [46]

    Separation and definability in fragments of two-variable first-order logic with counting,

    L. Kuijer, T. Tan, F. Wolter, and M. Zakharyaschev, “Separation and definability in fragments of two-variable first-order logic with counting,” in 40th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2025, Singapore, June 23-26, 2025. IEEE, 2025, pp. 329–343. [Onl...

    2025 doi

  39. [47]

    The convenience of tilings,

    P. van Emde Boas, “The convenience of tilings,” inComplexity, Logic, and Recursion Theory, 1997, pp. 331–363. 34 A Proofs for Section 3 Lemma 9.The following conditions are equivalent for allm: •m 1 ∧case(c 1),m 2 ∧case(c 2)are jointlyH(σ)-consistent; •m∈ Y ∗. Proof.Assumem= (...

    1997

  40. [48]

    , λ×|Type|}and a weakR-counting function with codomain{0,

    Moreover, if either condition holds forH ′,m, then they admit anR- counting function with codomain{0, . . . , λ×|Type|}and a weakR-counting function with codomain{0, . . . , λ}. Proof.We show (1). Only the right-to-left implication is nontrivial. Assume Ris a weakR-counting fu...

  41. [49]

    there is a uniform FO(σ)-interpolant forφS inH

  42. [50]

    there is a uniformH(σ)-interpolant forφS in FO. (Observe that (2)⇒(3) always holds.) To constructφS, regard the tilest∈ T as propositional variables and letσcontainT, the symbolsS, E,minintroduced in the paper, propositional variablesleft,right,top,bottom, and binary relations...

Pith tools

Reviewed May 21, 2026 · model on record in the stance chip above.