First-order answer set programming as constructive proof search
Open accessAbstract
We propose an interpretation of the first-order answer set programming (FOASP) in terms of intuitionistic proof theory. It is obtained by two polynomial translations between FOASP and the bounded-arity fragment of the \Sigma_1 level of the Mints hierarchy in first-order intuitionistic logic. It follows that \Sigma_1 formulas using predicates of fixed arity (in particular unary) are of the same strength as FOASP. Our construction reveals a close similarity between constructive provability and stable entailment, or equivalently, between the construction of an answer set and an intuitionistic refutation.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Conventional multimodal backbones are generally not flexible, and explicit fusion requires the presence of all modalities; missing any modality will break the training pipeline.
“Conventional backbones [31,39] are generally not flexible.”
From Are Multimodal Transformers Robust to Missing Modality? (2022) · cites this paper as [39]
Cites
Answer set programming at a glance
Brewka, G., Eiter, T., & Truszczyński, M. (2011) · Communications of the ACM · doi:10.1145/2043174.2043195 · Cited by 946 · see citing works
Complexity and expressive power of logic programming
Dantsin, E., Eiter, T., Gottlob, G., & Voronkov, A. (2001) · ACM Computing Surveys · doi:10.1145/502807.502810 · Cited by 739 · see citing works
Marek, W., & Truszczyński, M. (1991) · Journal of the ACM · doi:10.1145/116825.116836 · Cited by 418 · see citing works
What is answer set programming
Lifschitz, V. (2008) · National Conference on Artificial Intelligence · Cited by 330 · see citing works
Pearce, D. (2006) · Annals of Mathematics and Artificial Intelligence · doi:10.1007/s10472-006-9028-z · Cited by 171 · see citing works
Hereditarily sequential functionals
Nickau, H. (1994) · Lecture notes in computer science · doi:10.1007/3-540-58140-5_25 · Cited by 138 · see citing works
Kolaitis, P. G., & Papadimitriou, C. H. (1988) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/308386.308446 · Cited by 94 · see citing works
Stable inference as intuitionistic validity
Pearce, D. (1999) · The Journal of Logic Programming · doi:10.1016/s0743-1066(98)10015-8 · Cited by 86 · see citing works
Applications of intuitionistic logic in Answer Set Programming
Osorio, M., Navarro, J. A., & Arrazola, J. (2004) · Theory and Practice of Logic Programming · doi:10.1017/s1471068403001881 · Cited by 50 · see citing works
Operational semantics of resolution and productivity in Horn clause logic
Fu, P., & Komendantskaya, E. (2016) · Formal Aspects of Computing · doi:10.1007/s00165-016-0403-1 · Cited by 18 · see citing works
Intuitionistic Games: Determinacy, Completeness, and Normalization
Urzyczyn, P. (2016) · Studia Logica · doi:10.1007/s11225-016-9661-4 · Cited by 11 · see citing works
Self-citationOn the Mints Hierarchy in First-Order Intuitionistic Logic
Schubert, A., Urzyczyn, P., & Zdanowski, K. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-46678-0_29 · Cited by 8 · see citing works
Self-citationOn the Mints Hierarchy in First-Order Intuitionistic Logic
Schubert, A., Urzyczyn, P., & Zdanowski, K. (2017) · Logical Methods in Computer Science · doi:10.2168/lmcs-12(4:11)2016 · Cited by 6 · see citing works
Self-citationRestricted Positive Quantification Is Not Elementary
Schubert, A., Urzyczyn, P., & Walukiewicz-Chrząszcz, D. (2015) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.types.2014.251 · Cited by 3 · see citing works
Self-citationAnswer set programming in intuitionistic logic
Schubert, A., & Urzyczyn, P. (2017) · Indagationes Mathematicae · doi:10.1016/j.indag.2017.05.006 · Cited by 2 · see citing works
Self-citation
Flagged first, then by citations
1 of the 16 references couldn’t be matched to a known paper.
Cited by
Sorted by citations
Are Multimodal Transformers Robust to Missing Modality?
Ma, M., Ren, J., Zhao, L., Testuggine, D., & Peng, X. (2022) · 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr52688.2022.01764 · Cited by 198 · see citing works
A Review of Clustering Algorithms for Big Data
Djouzi, K., & Beghdad-Bey, K. (2019) · International Conference on Networking and Advanced Systems (ICNAS) · doi:10.1109/icnas.2019.8807822 · Cited by 41 · see citing works
MIS-AVoiDD: Modality Invariant and Specific Representation for Audio-Visual Deepfake Detection
Katamneni, V. S., & Rattani, A. (2023) · International Conference on Machine Learning and Applications · doi:10.1109/icmla58977.2023.00207 · Cited by 28 · see citing works
Zhao, X., Chen, Y., Chen, Y.-T., Liu, S., & Tang, B. (2022) · IEEE International Conference on Multimedia and Expo (ICME) · doi:10.1109/icme52920.2022.9859747 · Cited by 14 · see citing works
COMPASS: Contrastive Multimodal Pretraining for Autonomous Systems
Ma, S., Vemprala, S. H., Wang, W., Gupta, J. K., Song, Y., McDufft, D., & Kapoor, A. (2022) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros47612.2022.9982241 · Cited by 11 · see citing works
A Survey of the Proof-Theoretic Foundations of Logic Programming
Miller, D. (2021) · Theory and Practice of Logic Programming · doi:10.1017/s1471068421000533 · Cited by 9 · see citing works
Face-to-Face Contrastive Learning for Social Intelligence Question-Answering
Wilf, A., Ma, M. Q., Liang, P. P., Zadeh, A., & Morency, L. (2023) · International Conference on Automatic Face and Gesture Recognition · doi:10.1109/fg57933.2023.10042612 · Cited by 8 · see citing works
Exploring Missing Modality in Multimodal Egocentric Datasets
Ramazanova, M., Pardo, A., Alwassel, H., & Ghanem, B. (2025) · IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW) · doi:10.1109/cvprw67362.2025.00013 · Cited by 7 · see citing works
Querying as Prompt: Parameter-Efficient Learning for Multimodal Language Model
Liang, T., Huang, J., Kong, M. C., Chen, L., & Zhu, Q. (2024) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr52733.2024.02536 · Cited by 6 · see citing works
Multimodal Guidance Network for Missing- Modality Inference in Content Moderation
Zhao, Z., Palani, H., Liu, T., Evans, L., & Toner, R. (2024) · IEEE International Conference on Multimedia and Expo workshops · doi:10.1109/icmew63481.2024.10645412 · Cited by 5 · see citing works
Nguyen, C.-V. T., Nguyen, H.-S., Le, D.-T., & Ha, Q.-T. (2023) · International Conference on Knowledge and Systems Engineering/Proceedings · doi:10.1109/kse59128.2023.10299456 · Cited by 4 · see citing works
The New Normal: We Cannot Eliminate Cuts in Coinductive Calculi, But We Can Explore Them
Komendantskaya, E., Rozplokhas, D., & Basold, H. (2020) · Theory and Practice of Logic Programming · doi:10.1017/s1471068420000423 · Cited by 3 · see citing works
Fusion Techniques and Contextual Integration in Multimodal Sentiment Analysis
Vatsal, L. A., Tiwari, B., Upadhyay, L., & Sharma, T. (2025) · International Conference on Computing Technologies & Data Communication (ICCTDC) · doi:10.1109/icctdc64446.2025.11158728 · Cited by 2 · see citing works
Multimodal Sentiment Analysis with Missing Modality: A Knowledge-Transfer Approach
Liu, W., & Zhan, H. (2025) · Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC) · doi:10.1109/apsipaasc65261.2025.11249068 · Cited by 2 · see citing works
Hierarchical Fusion Network for Multimodal Sentiment Analysis
Hua, Y., Ji, R., Yang, S., Geng, Y., Gao, W., & Tan, Y. (2024) · IEEE International Conference on Pattern Recognition and Machine Learning (PRML) · doi:10.1109/prml62565.2024.10779845 · Cited by 2 · see citing works
G-TBML: GAN-enhanced Transformer-based Multimodal Binding Learning Model
Qu, W., & Wei, B. (2025) · International Conference on Machine Learning and Computer Application (ICMLCA) · doi:10.1109/icmlca66850.2025.11336479 · Cited by 1 · see citing works
Chen, W., Wu, J. Y., Nie, T., Xu, R., & Tu, L. (2025) · International Conference on the Frontiers of Electronic, Electrical and Information Engineering (ICFEEIE) · doi:10.1109/icfeeie66944.2025.00036 · Cited by 1 · see citing works
- Authors
- Schubert, A., & Urzyczyn, P.
- Affiliations
- University of Warsaw (PL)
- Venue
- EasyChair Preprints
- Publisher
- EasyChair
- Published
- 2018-05-31
- Volume
- 18
- Issue
- 3-4
- Pages
- 673-690
- ISSN
- 1471-0684 (ISSN-L)
- 2516-2314
- OpenAlex
- W2799131411
- Cited by
- 17
- References
- 16
- Citations by year
- 2025: 5 · 2024: 3 · 2023: 3 · 2022: 3 · 2021: 1 · 2020: 1 · 2019: 1
- FWCI
- 0.42
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Theory and Practice of Logic Programming (publishedVersion)
- EasyChair preprint (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, programming, and type systems
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Algebra and Logic
- Keywords
- translation between logics
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review