Horn Clauses for Verification and Synthesis

Many Program Verification and Synthesis problems of interest can be modeled directly using Horn clauses and many recent advances in the CLP and CAV communities have centered around efficiently solving problems presented as Horn clauses.

This series of workshops aims to bring together researchers working in the communities of Constraint/Logic Programming (e.g., ICLP and CP), Program Verification (e.g., CAV, TACAS, and VMCAI), and Automated Deduction (e.g., CADE, IJCAR), on the topic of Horn clause based analysis, verification, and synthesis.

Horn clauses for verification and synthesis have been advocated by these communities in different times and from different perspectives and HCVS is organized to stimulate interaction and a fruitful exchange and integration of experiences.

The workshop follows previous meetings: HCVS 2024 in Luxembourg (ETAPS 2024), HCVS 2023 in Paris (ETAPS 2023), HCVS 2022 in Munich (ETAPS 2022), HCVS 2021 in Luxembourg (online, ETAPS 2021), HCVS 2020 in Dublin, Ireland (ETAPS 2020), HCVS 2019 in Prague, Czech Republic (ETAPS 2019), HCVS 2018 in Oxford, UK (CAV, ICLP and IJCAR at FLoC 2018), HCVS 2017 in Gothenburg, Sweden (CADE 2017), HCVS 2016 in Eindhoven, The Netherlands (ETAPS 2016), HCVS 2015 in San Francisco, CA, USA (CAV 2015), and HCVS 2014 in Vienna, Austria (VSL).

Aims and Scope

Topics of interest include, but are not limited to the use of Horn clauses, constraints, and related formalisms in the following areas:

  • Analysis and verification of programs and systems of various kinds (e.g., imperative, object-oriented, functional, logic, higher-order, concurrent, transition systems, petri-nets, smart contracts)
  • Program synthesis
  • Program testing
  • Program transformation
  • Constraint solving
  • Type systems
  • Machine learning and automated reasoning
  • CHC encoding of analysis and verification problems
  • Resource analysis
  • Case studies and tools
  • Challenging problems
We solicit regular papers describing theory and implementation of Horn-clause based analysis and tool descriptions. We also solicit extended abstracts describing work-in-progress, as well as presentations covering previously published results that are of interest to the workshop.

Invited speakers

  • Grigory Fedyukovich (Florida State University, USA).
    Building Automated Reasoning Tools using the FreqHorn Framework

    Originally developed in 2017, the FreqHorn framework follows the Syntax-Guided Synthesis paradigm to automatically synthesize solutions for systems of Constrained Horn Clauses (CHC). Its distinguishing feature was the automatic construction of formal grammars for each uninterpreted predicate based on either its syntax, data, or bounded proofs based on Craig interpolation. Grammars are useful for the systematic enumeration of solution candidates and checking them with an SMT solver. Recently, the framework was extended to reason about CHCs with arrays, algebraic data types, and multi-phase systems.

    In this talk, I will give an overview of various features of FreqHorn that enable handling complex CHC systems. Moreover, I will demonstrate how its infrastructure has already been used to build CHC-based automated reasoning tools applicable for answering questions on program termination, program equivalence, precondition generation, and automated test case generation. Furthermore, FreqHorn is frequently used in teaching graduate-level courses on logic and program verification, in which students find it easy to extend and maintain.

  • Gennaro Parlato (University of Molise, Italy).
    Unifying Automata Theory and Constrained Horn Clauses for Scalable Program Verification

    In this talk, I present a body of work developed in collaboration with Marco Faella, exploring the intersection of automata theory and Constrained Horn Clauses (CHCs) to advance program verification and synthesis.

    We introduce Symbolic Data Tree Automata (SDTAs), a novel automata class generalizing classical tree automata through symbolic reasoning over structured data domains. SDTAs seamlessly integrate finite-state automata techniques with logical reasoning offered by CHCs, enabling robust and flexible analyses of computations on hierarchical or tree-shaped structures. While SDTA emptiness checking is generally undecidable, we demonstrate a practical reduction to CHC satisfiability, leveraging existing, efficient CHC solvers.

    To extend logical expressiveness, we propose MSO-D (Monadic Second-Order logic with Data), an extension of standard MSO on trees with predicates from an underlying data theory, designed for expressive reasoning about complex data structures. Although MSO-D is Turing-powerful in general, we identify a significant fragment whose satisfiability reduces directly to SDTA emptiness, thus facilitating automated verification using CHC solvers. This fragment retains considerable expressiveness, enabling characterization of diverse data structures commonly encountered in verification problems, as well as solving certain classes of infinite-state games.

    For linear-time specifications, we introduce an automata-theoretic approach for verifying properties expressed in LTLf^MT (Linear Temporal Logic over finite traces Modulo Theories). This logic augments LTLf with quantifier-free constraints from rich data theories. Our approach translates LTLf^MT into Symbolic Data Word Automata (SDWAs), where transitions are governed by theory constraints. Though satisfiability for both LTLf^MT and SDWAs is undecidable, our reduction to CHC satisfiability proves highly effective for model checking and runtime monitoring, as demonstrated by competitive experimental results against specialized tools.

    Finally, I present our latest work on verifying programs that manipulate dynamic, tree data structures—typically a challenging task requiring intricate, manual proofs. We introduce a unified framework based on knitted-tree encodings, which represent program executions as structured trees capturing inputs, outputs, and intermediate states. This compositional representation supports modular invariants and enables fully automated verification (e.g., memory safety) via CHC solvers. Our results demonstrate that this approach substantially simplifies and scales reasoning about complex, heap-manipulating programs.

Program

22 July 2025 (All times are in CEST) - Room: D-260 (D-building, 2nd floor)

08:30 - 08:55 Breakfast
 
08:55 - 09:00 Welcome (Emanuele De Angelis, Florian Frohn)
   
Session 1 (Chair: Florian Frohn)
9:00 - 10:00 Invited Talk: Building Automated Reasoning Tools using the FreqHorn Framework
Grigory Fedyukovich  
10:00 - 10:30 Semantic Properties of Computations Defined by Elementary Inference Systems
Salvador Lucas  
   
10:30 - 11:00 Coffee Break 
   
Session 2 (Chair: Florian Frohn)
11:00 - 11:30 Finding Regular Herbrand Models for CHCs using Answer Set Programming
Grégoire Maire and Thomas Genet  
11:30 - 12:00 CHC-COMP presentation
Gidon Ernst  
   
12:00 - 14:00 Lunch Break 
   
Session 3 (Chair: Emanuele De Angelis)
14:00 - 15:00 Invited Talk: Unifying Automata Theory and Constrained Horn Clauses for Scalable Program Verification
Gennaro Parlato  
15:00 - 15:30 Unsatisfiability Proofs for Horn Solving
Rodrigo Otoni, Martin Blicha, Matias Barandiaran Rivera, Patrick Eugster, Jan Kofroň and Natasha Sharygina  
   
15:30 - 16:00 Coffee Break 
   
Session 4 (Chair: Emanuele De Angelis)
16:00 - 16:30 CHCVERIF: A Portfolio-Based Solver for Constrained Horn Clauses
Mihály Dobos-Kovács, Levente Bajczi and András Vörös  
16:30 - 17:00 Theta as a Horn Solver
Levente Bajczi, Milán Mondok and Vince Molnár  
17:00 - 17:30 Infinite State Model Checking by Learning Transitive Relations
Florian Frohn and Jürgen Giesl  

Program Chairs

Program Committee

  • Nikolaj Bjørner, Microsoft, USA
  • Martin Blicha, University of Lugano, Switzerland
  • Konstantin Britikov, University of Lugano, Switzerland
  • Catherine Dubois, ENSIIE-Samovar, France
  • Gidon Ernst, Ludwig Maximilian University of Munich, Germany
  • Zafer Esen, Uppsala University, Sweden
  • Grigory Fedyukovich, Florida State University, USA
  • Carsten Fuhs, Birkbeck, University of London, UK
  • Hossein Hojjat, Tehran Institute for Advanced Studies, Iran
  • Petra Hozzová, Czech Technical University, Czechia
  • Lorenz Leutgeb, Max Planck Institute for Informatics, Germany
  • Pedro Lopez-Garcia, IMDEA Software Institute and Spanish Council for Scientific Research (CSIC), Spain
  • Dale Miller, INRIA and LIX/Institut Polytechnique de Paris, France
  • Jose F. Morales, IMDEA Software Research Institute, Spain
  • Sabina Rossi, Dipartimento di Informatica, Università Ca' Foscari di Venezia, Italy
  • Philipp Rümmer, University of Regensburg, Germany
  • Jonas Schöpf, University of Innsbruck, Austria
  • Wim Vanhoof, University of Namur, Belgium
  • German Vidal, MiST, VRAIN, Universitat Politecnica de Valencia, Spain

Submission

Submission has to be done in one of the following formats:

  • Extended abstracts (from half to 3 pages), which describe work in progress or aim to initiate discussions.
  • Presentation-only papers, i.e., papers already submitted or presented at a conference or another workshop. Such papers can be submitted in any format, and will not be included in the workshop post-proceedings.
  • Regular papers (up to 12 pages plus bibliography in EPTCS format), which should present previously unpublished work (completed or in progress), including descriptions of research, tools, and applications.
  • Tool papers (up to 4 pages in EPTCS format), which can outline the theoretical framework, the architecture, the usage, and experiments of the tool.
All submitted papers will be refereed by the program committee and will be selected for inclusion in the program in accordance with the referee reports. At least one author of each accepted paper will be required to attend the workshop to present the contribution. If enough regular papers are accepted, both regular papers and extended abstracts will be published electronically. The publication of a paper is not intended to preclude later publication. Full versions of extended abstracts, or substantial revisions, may later be published elsewhere.

Papers must be submitted through the EasyChair system using the web page: https://easychair.org/conferences/?conf=hcvs2025