Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 53 min ago
PreprintarXiv licencearXiv

More on expressibility of satisfiability in submodels and extensions

  • Nikolai L. Poliakov
  • Denis I. Saveliev
Open at sourcePDFDOICite

Abstract

We study expressibility in infinitary languages of the modal operators associated with satisfiability of sentences of these languages in submodels and extensions of models. We give a syntactic criterion for expressibility in finitary predicate languages, show that in many cases infinitary languages are closed under the operator associated with submodels, and that this is so in any language with a purely monadic signature. Finally, we prove that in finitary or strongly compact languages, the operator associated with extensions, though can be inexpressible by a single sentence, is always expressible by a universal theory, in striking contrast with the submodel case.

Related

  1. Active learning confidence measures for coupling strategies in digital twins integrating simulation and data-driven submodels
    Sylvain Chabanet, Hind Bril El-Haouzi, Philippe Thomas
    Simulation Modelling Practice and TheoryPeer-reviewedCC BY-NC 4.0Full text2 citedStatisticsHAL
  2. Do Neural Models Prefer Their Submodels?
    Alvaro Ribot, Yulia Alexandr, Anna Seigal
    arXivPreprintarXiv licenceFull textAlgebra & number theoryStatisticsarXiv
  3. Exact Complexity of the Satisfiability Problem for Strategy Logic
    Tikhon Pshenitsyn
    arXivPreprintCC BY 4.0Full textLogic & foundationsarXiv
  4. The rank of the random k-XORSAT matrix beyond satisfiability
    Amin Coja-Oghlan, Maurice Rolvien
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  5. An upper bound of 4.268 for the random 3-SAT satisfiability threshold
    Fedor Vorobyev
    arXivPreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{poliakov2026more,
  title = {{More on expressibility of satisfiability in submodels and extensions}},
  author = {Nikolai L. Poliakov and Denis I. Saveliev},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2605.02725},
  eprint = {2605.02725},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.02725},
}
RIS
TY  - UNPB
TI  - More on expressibility of satisfiability in submodels and extensions
AU  - Nikolai L. Poliakov
AU  - Denis I. Saveliev
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2605.02725
UR  - https://arxiv.org/abs/2605.02725
AB  - We study expressibility in infinitary languages of the modal operators associated with satisfiability of sentences of these languages in submodels and extensions of models. We give a syntactic criterion for expressibility in finitary predicate languages, show that in many cases infinitary languages are closed under the operator associated with submodels, and that this is so in any language with a purely monadic signature. Finally, we prove that in finitary or strongly compact languages, the operator associated with extensions, though can be inexpressible by a single sentence, is always expressible by a universal theory, in striking contrast with the submodel case.
ER  -