Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Succinct ordering and aggregation constraints in algebraic array theories
 
research article

Succinct ordering and aggregation constraints in algebraic array theories

Raya, Rodrigo  
•
Kuncak, Viktor  orcid-logo
August 1, 2024
Journal Of Logical And Algebraic Methods In Programming

We discuss two extensions to a recently introduced theory of arrays, which are based on considerations coming from the model theory of power structures. First, we discuss how the ordering relation on the index set can be expressed succinctly by referring to arbitrary Venn regions. Second, we show how to add general aggregators to the calculus. The result is a logic that subsumes four previous fragments discussed in the literature and is distinct from array fold logic, in that it can express summations, while its satisfiability problem remains in non -deterministic polynomial time.

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.1016/j.jlamp.2024.100978
Web of Science ID

WOS:001249137100001

Author(s)
Raya, Rodrigo  
Kuncak, Viktor  orcid-logo
Date Issued

2024-08-01

Publisher

Elsevier Science Inc

Published in
Journal Of Logical And Algebraic Methods In Programming
Volume

140

Article Number

100978

Subjects

Technology

•

Decision Procedures

•

Satisfiability Modulo Theories

•

Arrays

•

Feferman-Vaught

•

Composition Theorems

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LARA  
FunderGrant Number

Swiss NSF Project

P500PT_222338

Available on Infoscience
July 3, 2024
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/209098
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés