Valeria Fionda

AAAI Conference 2026 Conference Paper

Computing Syntax Tree-based Minimal Unsatisfiable Cores of LTLf Formulas

• Valeria Fionda
• Antonio Ielo
• Francesco Ricca

Linear Temporal Logic on Finite Traces (LTLf) is a popular logic to express declarative specifications in Artificial Intelligence (AI). The recent call for explainable AI tools has made relevant the problem of computing efficiently minimal unsatisfiable cores (MUCs) and minimal correction sets (MCSes) of LTLf formulas. Recent work has focused on the extraction of MUCs on formulas in conjunctive form. In this paper, we present a method that operates on arbitrary formulas and computes a more refined notion of MUCs, as introduced by Schuppan, along with the corresponding notion of MCSes. Experiments show that our system, based on Answer Set Programming, outperforms available tools.

IJCAI Conference 2025 Conference Paper

Are Large Language Models Fluent in Declarative Process Mining?

• Valeria Fionda
• Antonio Ielo
• Francesco Ricca

Recent advancements in AI have made LLMs valuable tools for automating the interpretation of textual descriptions of business processes and for converting formal process specifications into natural language. However, there are no practical methodologies or systematic assessments to ensure these automatic translations are faithful. This paper proposes a novel approach, based on an auxiliary bidirectional translation task, to assess LLMs performance quantitatively; also, it also empirically evaluates the performance of state-of-the-art LLMs for bidirectional translations between natural language and declarative formal process specifications. The results reveal substantial variability in performance among the LLMs, highlighting the importance of LLM selection and confirming the need for a robust method for assessing LLMs' outputs.

ECAI Conference 2024 Conference Paper

Bipartite Time Series Network for Data Imputation

• Ilaria Lucrezia Amerise
• Valeria Fionda
• Giuseppe Pirrò

The pervasive issue of missing data in statistical analysis and data science significantly impacts the integrity and accuracy of Time-Series Cross-Sectional (TSCS) datasets, extensively used in domains like health sciences and sensor applications. Traditional imputation methods are often inadequate for these datasets as they fail to address the complexities arising from cross-sectional and temporal data gaps. This paper introduces BiTSNet (Bipartite Time Series Network for Data Imputation), a novel approach designed to tackle the unique challenges of TSCS datasets by leveraging a dual representation of data. BiTSNet models cross-sectional time series data as sequences of bipartite graphs, where each graph represents a specific time step, and feature values are depicted as edge weights. Thus, missing values are interpreted as missing edge feature values, allowing BiTSNet to comprehensively capture spatial relationships within each time step and temporal relationships across steps. The framework uses Graph Neural Networks (GNNs) to process spatial dependencies within these bipartite graph representations and employs Recurrent Neural Networks (RNNs) to handle temporal dependencies. This integration enables BiTSNet to learn the intricate intra-time step relationships and the inter-time step dynamics effectively. Our approach not only preserves the longitudinal and cross-sectional integrity of the data but also ensures the production of valid and insightful conclusions from the enriched dataset. We evaluated BiTSNet on several datasets and compared it against the state-of-the-art approaches with encouraging results.

KR Conference 2023 Conference Paper

Logic-based Composition of Business Process Models

• Valeria Fionda
• Antonio Ielo
• Francesco Ricca

Process Mining is a family of techniques that exploit data collected from process execution to analyze and improve process efficiency, quality, and security. Over the years, many modeling languages have been proposed for process model specification, with different expressiveness, features, and computational properties. We propose a new logic-based declarative formalism, called Constraint Formulae, to compose process specifications, expressed in heterogeneous process modeling languages, without altering their original semantics. We formalize common process mining tasks for Constraint Formulae, study their computational properties, and provide an implementation in Answer Set Programming.

ECAI Conference 2023 Conference Paper

On the Effectiveness of Compact Strategies for Opinion Diffusion in Social Environments

• Carlo Adornetto
• Valeria Fionda
• Gianluigi Greco

An opinion diffusion scenario is considered where two marketers compete to diffuse their own opinions over a social network. In particular, they implement social proof marketing approaches that naturally give rise to a strategic setting, where it is crucial to find the appropriate order for targeting the individuals to which provide the incentives to adopt their opinions. The setting is extensively studied from the theoretical and empirical viewpoint, by considering strategies defined in a compact way, such as those that can be defined by selecting the individuals according to their degree of centrality in the underlying network. In addition to depicting a clear picture of the complexity issues arising in the setting, several compact strategies are empirically compared on real-world social networks. Results suggest that the effectiveness of compact strategies is moderately influenced by the characteristic of the network, with some centrality measures naturally emerging as good candidates to define heuristic approaches for marketing campaigns.

IJCAI Conference 2022 Conference Paper

LTL on Weighted Finite Traces: Formal Foundations and Algorithms

• Carmine Dodaro
• Valeria Fionda
• Gianluigi Greco

LTL on finite traces (LTLf ) is a logic that attracted much attention in recent literature, for its ability to formalize the qualitative behavior of dynamical systems in several application domains. However, its practical usage is still rather limited, as LTLf cannot deal with any quantitative aspect, such as with the costs of realizing some desired behaviour. The paper fills the gap by proposing a weighting framework for LTLf encoding such quantitative aspects in the traces over which it is evaluated. The complexity of reasoning problems on weighted traces is analyzed and compared to that of standard LTLf, by considering arbitrary formulas as well as classes of formulas defined in terms of relevant syntactic restrictions. Moreover, a reasoner for LTL on weighted finite traces is presented, and its performances are assessed on benchmark data.

AAAI Conference 2020 Conference Paper

Learning Triple Embeddings from Knowledge Graphs

• Valeria Fionda
• Giuseppe Pirrò

Graph embedding techniques allow to learn high-quality feature vectors from graph structures and are useful in a variety of tasks, from node classification to clustering. Existing approaches have only focused on learning feature vectors for the nodes and predicates in a knowledge graph. To the best of our knowledge, none of them has tackled the problem of directly learning triple embeddings. The approaches that are closer to this task have focused on homogeneous graphs involving only one type of edge and obtain edge embeddings by applying some operation (e. g. , average) on the embeddings of the endpoint nodes. The goal of this paper is to introduce Triple2Vec, a new technique to directly embed knowledge graph triples. We leverage the idea of line graph of a graph and extend it to the context of knowledge graphs. We introduce an edge weighting mechanism for the line graph based on semantic proximity. Embeddings are finally generated by adopting the SkipGram model, where sentences are replaced with graph walks. We evaluate our approach on different realworld knowledge graphs and compared it with related work. We also show an application of triple embeddings in the context of user-item recommendations.

AAMAS Conference 2019 Conference Paper

Maximizing the Spread of an Opinion when Tertium Datur Est

• Vincenzo Auletta
• Diodato Ferraioli
• Valeria Fionda
• Gianluigi Greco

IJCAI Conference 2018 Conference Paper

Fact Checking via Evidence Patterns

• Valeria Fionda
• Giuseppe Pirrò

We tackle fact checking using Knowledge Graphs (KGs) as a source of background knowledge. Our approach leverages the KG schema to generate candidate evidence patterns, that is, schema-level paths that capture the semantics of a target fact in alternative ways. Patterns verified in the data are used to both assemble semantic evidence for a fact and provide a numerical assessment of its truthfulness. We present efficient algorithms to generate and verify evidence patterns, and assemble evidence. We also provide a translation of the core of our algorithms into the SPARQL query language. Not only our approach is faster than the state of the art and offers comparable accuracy, but it can also use any SPARQL-enabled KG.

JAIR Journal 2018 Journal Article

LTL on Finite and Process Traces: Complexity Results and a Practical Reasoner

• Valeria Fionda
• Gianluigi Greco

Linear temporal logic (LTL) is a modal logic where formulas are built over temporal operators relating events happening in different time instants. According to the standard semantics, LTL formulas are interpreted on traces spanning over an infinite timeline. However, applications related to the specification and verification of business processes have recently pointed out the need for defining and reasoning about a variant of LTL, which we name LTLp, whose semantics is defined over process traces, that is, over finite traces such that, at each time instant, precisely one propositional variable (standing for the execution of some given activity) evaluates true. The paper investigates the theoretical underpinnings of LTLp and of a related logic formalism, named LTLf, which had already attracted attention in the literature and where formulas have the same syntax as in LTLp and are evaluated over finite traces, but without any constraint on the number of variables simultaneously evaluating true. The two formalisms are comparatively analyzed, by pointing out similarities and differences. In addition, a thorough complexity analysis has been conducted for reasoning problems about LTLp and LTLf, by considering arbitrary formulas as well as classes of formulas defined in terms of restrictions on the temporal operators that are allowed. Finally, based on the theoretical findings of the paper, a practical reasoner specifically tailored for LTLp and LTLf has been developed by leveraging state-of-the-art SAT solvers. The behavior of the reasoner has been experimentally compared with other systems available in the literature.

AIJ Journal 2016 Journal Article

Building knowledge maps of Web graphs

• Valeria Fionda
• Claudio Gutierrez
• Giuseppe Pirrò

AAAI Conference 2016 Conference Paper

The Complexity of LTL on Finite Traces: Hard and Easy Fragments

• Valeria Fionda
• Gianluigi Greco

This paper focuses on LTL on finite traces (LTLf ) for which satisfiability is known to be PSPACE-complete. However, little is known about the computational properties of fragments of LTLf. In this paper we fill this gap and make the following contributions. First, we identify several LTLf fragments for which the complexity of satisfiability drops to NP-complete or even P, by considering restrictions on the temporal operators and Boolean connectives being allowed. Second, we study a semantic variant of LTLf, which is of interest in the domain of business processes, where models have the property that precisely one propositional variable evaluates true at each time instant. Third, we introduce a reasoner for LTLf and compare its performance with the state of the art.

AAAI Conference 2015 Conference Paper

Extended Property Paths: Writing More SPARQL Queries in a Succinct Way

• Valeria Fionda
• Giuseppe Pirrò
• Mariano Consens

We introduce Extended Property Paths (EPPs), a significant enhancement of SPARQL property paths. EPPs allow to capture in a succinct way a larger class of navigational queries than property paths. We present the syntax and formal semantics of EPPs and introduce two different evaluation strategies. The first is based on an algorithm implemented in a custom query processor. The second strategy leverages a translation algorithm of EPPs into SPARQL queries that can be executed on existing SPARQL processors. We compare the two evaluation strategies on real data to highlight their pros and cons.

AAAI Conference 2015 Conference Paper

Trust Models for RDF Data: Semantics and Complexity

• Valeria Fionda
• Gianluigi Greco

Due to the openness and decentralization of the Web, mechanisms to represent and reason about the reliability of RDF data become essential. This paper embarks on a formal analysis of RDF data enriched with trust information by focusing on the characterization of its model-theoretic semantics and on the study of relevant reasoning problems. The impact of trust values on the computational complexity of well-known concepts related to the entailment of RDF graphs is studied. In particular, islands of tractability are identified for classes of acyclic and nearly-acyclic graphs. Moreover, an implementation of the framework and an experimental evaluation on real data are discussed.

KR Conference 2014 Short Paper

Knowledge Maps of Web Graphs

• Valeria Fionda
• Claudio Gutierrez
• Giuseppe Pirró

In this short note we give an overview of our research concerning cartography on the Web and its challenges. We present a mathematical formalism to capture the notion of map on the Web, which allows to automatize the construction of maps. 1 Terry Gilliam Tim Burton Influeces between directors Stanley Kubrick Orson Welles Cartography is the art of making maps. Its essential aim is that of representing the characteristics of a region of interest. Cartography builds upon two main steps: selection and abstraction (Robinson et al. 1995). Selection enables to focus only on the particular pieces of information that will serve the map’s purpose; in this phase the region of the space to be mapped is chosen. Abstraction is the fundamental property of a map, which states that a map should be smaller than the region it portraits. Thus, a map can be simply defined as an abstract representation of a region of interest. The Web is a large and interconnected information space commonly accessed and explored via navigation. This space is simply too large and its interrelations too complex for anyone to grasp its content by direct observation. Hence, the possibility of applying cartographic principles to the Web space becomes a relevant matter. Knowledge maps can be useful cues that help to navigate, find routes and discover previously unknown connections between knowledge items on the Web. Effectively, they can play the role of navigational charts helping users to cope with the size of the Web (cyber)space (Dodge and Kitchin 2001). Users via knowledge maps can track, record, identify and abstract conceptual regions of information on the Web, for their own use, for sharing/exchanging with other users and/or for further processing (e. g., combination with other maps). Maps are also useful to analyze information. For instance, the availability of a series of chronologically sequential maps enables complex map analysis (e. g., longitudinal analysis) for the detection and forecasting of trends in specific domains (Garfield 1994). This is useful, for instance, in the analysis of the knowledge flows in scientific literature, which helps in understating how the interlinking between disciplines is changing (Rosvall and Bergstrom 2008). Maps of social networks Lars von Trier Woody Allen John Ford

AIJ Journal 2013 Journal Article

The complexity of mixed multi-unit combinatorial auctions: Tractability under structural and qualitative restrictions

• Valeria Fionda
• Gianluigi Greco

ECAI Conference 2012 Conference Paper

CAKES: Cross-lingual Wikipedia Knowledge Enrichment and Summarization

• Valeria Fionda
• Giuseppe Pirrò

Wikipedia is a huge source of multilingual knowledge curated by human contributors. Wiki articles are independently written in the various languages and may cover different perspectives about a given subject. The aim of this paper is to exploit Wikipedia multilingual information for knowledge enrichment and summarization. Investigating the link structure of a Wiki article in a source language and comparing it with the structure of articles about the same subject written in other languages gives insights about the body of knowledge shared among languages. This investigation is also useful to identify knowledge perspectives not covered in the source language but covered in other languages. We implemented these ideas in CAKES, which: i) exploits Wikipedia information on the fly without requiring any data preprocessing; ii) enables to specify the set of languages to be considered and; iii) ranks subjects interesting for a given article on the basis of their popularity among languages.

IJCAI Conference 2009 Conference Paper

• Valeria Fionda
• Gianluigi Greco

Mixed multi-unit combinatorial auctions (MMU- CAs) are extensions of classical combinatorial auctions (CAs) where bidders trade transformations of goods rather than just sets of goods. Solving MMUCAs, i. e. , determining the sequences of bids to be accepted by the auctioneer, is computationally intractable in general. However, differently from CAs, little was known about whether polynomialtime solvable classes of MMUCAs can be singled out based on constraining their characteristics. The paper precisely fills this gap, by depicting a clear picture of the “tractability frontier” for MMUCA instances under both structural and qualitative restrictions, which characterize interactions among bidders and types of bids involved in the various transformations, respectively. By analyzing these restrictions, a sharp frontier is charted based on various dichotomy results. In particular, tractability islands resulting from the investigation generalize on MMUCAs the largest class of tractable CAs emerging from the literature.