Search

There is a growing need to perform real-time analytics on dynamic graphs in order to deliver the values of big data to users. An important problem from such applications is continuously identifying and monitoring critical patterns when fine-grained updates at a high velocity occur on the graphs. A lot of efforts have been made to develop practical solutions for these problems. Despite the efforts, existing algorithms showed limited running time and scalability in dealing with large and/or many graphs. In this paper, we study the problem of continuous multi-query optimization for subgraph matching over dynamic graph data. (1) We propose annotated query graph, which is obtained by merging the multi-queries into one. (2) Based on the annotated query, we employ a concise auxiliary data structure to represent partial solutions in a compact form. (3) In addition, we propose an efficient maintenance strategy to detect the affected queries for each update and report corresponding matches in one pass. (4) Extensive experiments over real-life and synthetic datasets verify the effectiveness and efficiency of our approach and confirm a two orders of magnitude improvement of the proposed solution. [ABSTRACT FROM AUTHOR]

With the increase of data volume in heterogeneous datasets that are being published following Open Data initiatives, new operators are necessary to help users to find the subset of data that best satisfies their preference criteria. Quantitative approaches such as top-k queries may not be the most appropriate approaches as they require the user to assign weights that may not be known beforehand to a scoring function. Unlike the quantitative approach, under the qualitative approach, which includes the well-known skyline, preference criteria are more intuitive in certain cases and can be expressed more naturally. In this paper, we address the problem of evaluating SPARQL qualitative preference queries over an Ontology-Based Data Access (OBDA) approach, which provides uniform access over multiple and heterogeneous data sources. Our main contribution is Morph-Skyline++, a framework for processing SPARQL qualitative preferences by directly querying relational databases. Our framework implements a technique that translates SPARQL qualitative preference queries directly into queries that can be evaluated by a relational database management system. We evaluate our approach over different scenarios, reporting the effects of data distribution, data size, and query complexity on the performance of our proposed technique in comparison with state-of-the-art techniques. Obtained results suggest that the execution time can be reduced by up to two orders of magnitude in comparison to current techniques scaling up to larger datasets while identifying precisely the result set. [ABSTRACT FROM AUTHOR]

Ontology matching is a research area aimed at finding ways to make different ontologies interoperable. Solutions to the problem have been proposed from different disciplines, including databases, natural language processing, and machine learning. The role of foundational ontologies for ontology matching is an important one, as they provide a well-founded reference model that can be shared across domains. It is multifaceted and with room for development. This paper presents an overview of the different tasks involved in ontology matching that consider foundational ontologies. We discuss the strengths and weaknesses of existing proposals and highlight the challenges to be addressed in the future. [ABSTRACT FROM AUTHOR]

Graph embeddings play a significant role in the design and analysis of parallel algorithms. It is a mapping of the topological structure of a guest graph G into a host graph H, which is represented as a one-to-one mapping from the vertex set of the guest graph to the vertex set of the host graph. In multiprocessing systems, the interconnection networks enhance the efficient communication between the components in the system. Obtaining minimum wirelength in embedding problems is significant in the designing of networks and simulating one architecture by another. In this paper, we determine the wirelength of embedding 3-ary n-cubes into cylinders and certain trees. [ABSTRACT FROM AUTHOR]

Multilattices are generalisations of lattices introduced by Mihail Benado in [4]. He replaced the existence of unique lower (resp. upper) bound by the existence of maximal lower (resp. minimal upper) bound(s). A multilattice will be called pure if it is not a lattice. Multilattices could be endowed with a residuation, and therefore used as set of truth-values to evaluate elements in fuzzy setting. In this paper we exhibit the smallest pure multilattice and show that it is a sub-multilattice of any pure multilattice. We also prove that any bounded residuated multilattice that is not a residuated lattice has at least seven elements. We apply the ordinal sum construction to get more examples of residuated multilattices that are not residuated lattices. We then use these residuated multilattices to evaluate objects and attributes in formal concept analysis setting, and describe the structure of the set of corresponding formal concepts. More precisely, if i := (Ai, ≤i, ⊤i, ⊙i, →i, ⊥i), i = 1, 2 are two complete residuated multilattices, G and M two nonempty sets and (ϕ, ψ) a Galois connection between A 1 G and A 2 M that is compatible with the residuation, then we show that : = { (h , f) ∈ A 1 G × A 2 M ; φ (h) = f and ψ (f) = h } can be endowed with a complete residuated multilattice structure. This is a generalization of a result by Ruiz-Calviño and Medina [20] saying that if the (reduct of the) algebras i, i = 1; 2 are complete multilattices, then is a complete multilattice. [ABSTRACT FROM AUTHOR]

Indexing is a well-known database technique used to facilitate data access and speed up query processing. Nevertheless, the construction and modification of indexes are very expensive. In traditional approaches, all records in the database table are equally covered by the index. It is not effective, since some records may be queried very often and some never. To avoid this problem, adaptive merging has been introduced. The key idea is to create an index adaptively and incrementally as a side-product of query processing. As a result, the database table is indexed partially depending on the query workload. This paper faces the problem of adaptive merging for phase change memory (PCM). The most important features of this memory type are limited write endurance and high write latency. As a consequence, adaptive merging should be investigated from the scratch. We solve this problem in two steps. First, we apply several PCM optimization techniques to the traditional adaptive merging approach. We prove that the proposed method (eAM) outperforms a traditional approach by 60%. After that, we invent the framework for adaptive merging (PAM) and propose a new variant of the PCM-optimized index. It further improves the system performance by 20% for databases where search queries interleave with data modifications. [ABSTRACT FROM AUTHOR]

The notion of aggregator oblivious (AO) security for privacy preserving data aggregation was formalized with a specific construction of AO-secure blinding technique over a cyclic group by Shi et al. Some of proposals of data aggregation protocols use the blinding technique of Shi et al. for BGN cryptosystem, an additive homomorphic encryption. Previously, there have been some security analysis on some of BGN based data aggregation protocols in the context of integrity or authenticity of data. Even with such security analysis, the BGN cryptosystem has been a popular building block of privacy preserving data aggregation protocol. In this paper, we study the privacy issues in the blinding technique of Shi et al. used for BGN cryptosystem. We show that the blinding techniques for the BGN cryptosystem used in several protocols are not privacy preserving against the recipient, the decryptor. Our analysis is based on the fact that the BGN cryptosystem uses a pairing e : G × G → GT and the existence of the pairing makes the DDH problem on G easy to solve. We also suggest how to prevent such privacy leakage in the blinding technique of Shi et al. used for BGN cryptosystem. [ABSTRACT FROM AUTHOR]

With the increasing popularity of knowledge graph (KG), many applications such as sentiment analysis, trend prediction, and question answering use KG for better performance. Despite the obvious usefulness of commonsense and factual information in the KGs, to the best of our knowledge, KGs have been rarely integrated into the task of answer selection in community question answering (CQA). In this paper, we propose a novel answer selection method in CQA by using the knowledge embedded in KGs. We also learn a latent-variable model for learning the representations of the question and answer, jointly optimizing generative and discriminative objectives. It also uses the question category for producing context-aware representations for questions and answers. Moreover, the model uses variational autoencoders (VAE) in a multi-task learning process with a classifier to produce class-specific representations for answers. The experimental results on three widely used datasets demonstrate that our proposed method is effective and outperforms the existing baselines significantly. [ABSTRACT FROM AUTHOR]

With the rapid development of neural networks, much attention has been focused on network embedding for complex network data, which aims to learn low-dimensional embedding of nodes in the network and how to effectively apply learned network representations to various graph-based analytical tasks. Two typical models exist namely the shallow random walk network representation method and deep learning models such as graph convolution networks (GCNs). The former one can be used to capture the linear structure of the network using depth-first search (DFS) and width-first search (BFS), whereas Hierarchical GCN (HGCN) is an unsupervised graph embedding that can be used to describe the global nonlinear structure of the network via aggregating node information. However, the two existing kinds of models cannot simultaneously capture the nonlinear and linear structure information of nodes. Thus, the nodal characteristics of nonlinear and linear structures are explored in this paper, and an unsupervised representation method based on HGCN that joins learning of shallow and deep models is proposed. Experiments on node classification and dimension reduction visualization are carried out on citation, language, and traffic networks. The results show that, compared with the existing shallow network representation model and deep network model, the proposed model achieves better performances in terms of micro-F1, macro-F1 and accuracy scores. [ABSTRACT FROM AUTHOR]

Knowledge graphs such as DBpedia, Freebase or Wikidata always contain a taxonomic backbone that allows the arrangement and structuring of various concepts in accordance with hypo-hypernym ("class-subclass") relationship. With the rapid growth of lexical resources for specific domains, the problem of automatic extension of the existing knowledge bases with new words is becoming more and more widespread. In this paper, we address the problem of taxonomy enrichment which aims at adding new words to the existing taxonomy. We present a new method which allows achieving high results on this task with little effort. It uses the resources which exist for the majority of languages, making the method universal. We extend our method by incorporating deep representations of graph structures like node2vec, Poincaré embeddings, GCN etc. that have recently demonstrated promising results on various NLP tasks. Furthermore, combining these representations with word embeddings allows us to beat the state of the art. We conduct a comprehensive study of the existing approaches to taxonomy enrichment based on word and graph vector representations and their fusion approaches. We also explore the ways of using deep learning architectures to extend taxonomic backbones of knowledge graphs. We create a number of datasets for taxonomy extension for English and Russian. We achieve state-of-the-art results across different datasets and provide an in-depth error analysis of mistakes. [ABSTRACT FROM AUTHOR]

Topic evolution helps the understanding of current research topics and their histories by automatically modeling and detecting the set of shared research fields in academic publications as topics. This paper provides a generalized analysis of the topic evolution method for predicting the emergence of new topics, which can operate on any dataset where the topics are defined as the relationships of their neighborhoods in the past by extrapolating to the future topics. Twenty sample topic networks were built with various fields-of-study keywords as seeds, covering domains such as business, materials, diseases, and computer science from the Microsoft Academic Graph dataset. The binary classifier was trained for each topic network using 15 structural features of emerging and existing topics and consistently resulted in accuracy and F1 over 0.91 for all twenty datasets over the periods of 2000 to 2019. Feature selection showed that the models retained most of the performance with only one-third of the tested features. Incremental learning was tested within the same topic over time and between different topics, which resulted in slight performance improvements in both cases. This indicates there is an underlying pattern to the neighbors of new topics common to research domains, likely beyond the sample topics used in the experiment. The result showed that network-based new topic prediction can be applied to various research domains with different research patterns. [ABSTRACT FROM AUTHOR]

Knowledge Graph Embeddings, i.e., projections of entities and relations to lower dimensional spaces, have been proposed for two purposes: (1) providing an encoding for data mining tasks, and (2) predicting links in a knowledge graph. Both lines of research have been pursued rather in isolation from each other so far, each with their own benchmarks and evaluation methodologies. In this paper, we argue that both tasks are actually related, and we show that the first family of approaches can also be used for the second task and vice versa. In two series of experiments, we provide a comparison of both families of approaches on both tasks, which, to the best of our knowledge, has not been done so far. Furthermore, we discuss the differences in the similarity functions evoked by the different embedding approaches. [ABSTRACT FROM AUTHOR]

In this paper we describe an argumentation-based representation of normal form games, and demonstrate how argumentation can be used to compute pure strategy Nash equilibria. Our approach builds on Modgil's Extended Argumentation Frameworks. We demonstrate its correctness, showprove several theoretical properties it satisfies, and outline how it can be used to explain why certain strategies are Nash equilibria to a non-expert human user. [ABSTRACT FROM AUTHOR]

This paper presents the universal address sequence generator (UASG) for memory built-in-self-test. The studies are based on the proposed universal method for generating address sequences with the desired properties for multirun march memory tests. As a mathematical model, a modification of the recursive relation for quasi-random sequence generation is used. For this model, a structural diagram of the hardware implementation is given, of which the basis is a storage device for storing so-called direction numbers of the generation matrix. The form of the generation matrix determines the basic properties of the generated address sequences. The proposed UASG generates a wide spectrum of different address sequences, including the standard ones, such as linear, address complement, gray code, worst-case gate delay, 2i, next address, and pseudorandom. Examples of the use of the proposed methods are considered. The result of the practical implementation of the UASG is presented, and the main characteristics are evaluated. [ABSTRACT FROM AUTHOR]

Given a subset of X ⊆ ℝn we can associate with every point x ∈ ℝn a vector space V of maximal dimension with the property that for some ball centered at x, the subset X coincides inside the ball with a union of lines parallel to V. A point is singular if V has dimension 0. In an earlier paper we proved that a 〈ℝ, +, <, ℤ〉-definable relation X is 〈ℝ, +, <, 1〉-definable if and only if the number of singular points is finite and every rational section of X is 〈R, +, <, 1〉-definable, where a rational section is a set obtained from X by fixing some component to a rational value. Here we show that we can dispense with the hypothesis of X being 〈ℝ, +, <, ℤ〉-definable by requiring that the components of the singular points be rational numbers. This provides a topological characterization of first-order definability in the structure 〈ℝ, +, <, 1〉. It also allows us to deliver a self-definable criterion (in Muchnik's terminology) of 〈ℝ, +, <, 1〉- and 〈ℝ, +, <,ℤ〉-definability for a wide class of relations, which turns into an effective criterion provided that the corresponding theory is decidable. In particular these results apply to the class of so-called k–recognizable relations which are defined by finite Muller automata via the representation of the reals in a integer basis k, and allow us to prove that it is decidable whether a k–recognizable relation (of any arity) is l–recognizable for every base l ≥ 2. [ABSTRACT FROM AUTHOR]

In Petri net synthesis we ask whether a given transition system A can be implemented by a Petri net N. Depending on the level of accuracy, there are three ways how N can implement A: an embedding, the least accurate implementation, preserves only the diversity of states of A; a language simulation already preserves exactly the language of A; a realization, the most accurate implementation, realizes the behavior of A exactly. However, whatever the sought implementation, a corresponding net does not always exist. In this case, it was suggested to modify the input behavior – of course as little as possible. Since transition systems consist of states, events and edges, these components appear as a natural choice for modifications. In this paper we show that the task of converting an unimplementable transition system into an implementable one by removing as few states or events or edges as possible is NP-complete –regardless of what type of implementation we are aiming for; we also show that the corresponding parameterized problems are W[2]-hard, where the number of removed components is considered as the parameter; finally, we show there is no c-approximation algorithm (with a polynomial running time) for neither of these problems, for every constant c ≥ 1. [ABSTRACT FROM AUTHOR]

Petri net synthesis consists in deciding for a given transition system A whether there exists a Petri net N whose reachability graph is isomorphic to A. Several works examined the synthesis of Petri net subclasses that restrict, for every place p of the net, the cardinality of its preset or of its postset or both in advance by small natural numbers ϱ and κ, respectively, such as for example (weighted) marked graphs, (weighted) T-systems and choice-free nets. In this paper, we study the synthesis aiming at Petri nets which have such restricted place environments, from the viewpoint of classical and parameterized complexity: We first show that, for any fixed natural numbers ϱ and κ, deciding whether for a given transition system A there is a Petri net N such that (1) its reachability graph is isomorphic to A and (2) for every place p of N the preset of p has at most ϱ and the postset of p has at most κ elements is doable in polynomial time. Secondly, we introduce a modified version of the problem, namely ENVIRONMENTRESTRICTEDSYNTHESIS (ERS, for short), where ϱ and κ are part of the input, and show that ERS is NPcomplete, regardless whether the sought net is impure or pure. In case of the impure nets, our methods also imply that ERS parameterized by ϱ + κ is W[2]-hard. [ABSTRACT FROM AUTHOR]

The first part of the paper is an introduction to the theory of probabilistic concurrent systems under a partial order semantics. Key definitions and results are given and illustrated on examples. The second part includes contributions. We introduce deterministic concurrent systems as a subclass of concurrent systems. Deterministic concurrent system are "locally commutative" concurrent systems. We prove that irreducible and deterministic concurrent systems have a unique probabilistic dynamics, and we characterize these systems by means of their combinatorial properties. ACM CSS: G.2.1; F.1.1 [ABSTRACT FROM AUTHOR]

The paper presents a secure and usable variant of the Game Changer Password System, first proposed by McLennan, Manning, and Tuft. Unlike the initial proposal based on inadequately secure Monopoly and Chess, we propose an improved version based on a layered "Battleship" game resilient against brute force and dictionary attacks. Since the initially proposed scheme did not check for the memorability and usability of a layered version, we conducted an experiment on the usability and memorability aspects. Surprisingly, layered passwords are just as memorable as single ones and, with an 80% recall rate, comparable to other graphical password systems. The claim that memorability is the most vital aspect of game-based password systems cannot be disproved. However, the experiment revealed that the usability decreased to such a low level that users felt less inclined to use such a system daily or recommend it to others. Our study has once again shown that optimizing the password security–memorability–usability triangle is hard to achieve without compromising one of its cornerstones. However, the layered Game Changer Password System can be used in specific applications where usability is of secondary importance, while security and memorability augmented by its graphical interface are at the forefront. [ABSTRACT FROM AUTHOR]

Multidimensional scaling (MDS) is a widely used technique for mapping data from a high-dimensional to a lower-dimensional space and for visualizing data. Recently, a new method, known as Geometric MDS, has been developed to minimize the MDS stress function by an iterative procedure, where coordinates of a particular point of the projected space are moved to the new position defined analytically. Such a change in position is easily interpreted geometrically. Moreover, the coordinates of points of the projected space may be recalculated simultaneously, i.e. in parallel, independently of each other. This paper has several objectives. Two implementations of Geometric MDS are suggested and analysed experimentally. The parallel implementation of Geometric MDS is developed for multithreaded multi-core processors. The sequential implementation is optimized for computational speed, enabling it to solve large data problems. It is compared with the SMACOF version of MDS. Python codes for both Geometric MDS and SMACOF are presented to highlight the differences between the two implementations. The comparison was carried out on several aspects: the comparative performance of Geometric MDS and SMACOF depending on the projection dimension, data size and computation time. Geometric MDS usually finds lower stress when the dimensionality of the projected space is smaller. [ABSTRACT FROM AUTHOR]

In this paper, we give an overview of some recent work on applying tools from category theory in finite model theory, descriptive complexity, constraint satisfaction, and combinatorics. The motivations for this work come from Computer Science, but there may also be something of interest for model theorists and other logicians. The basic setting involves studying the category of relational structures via a resource-indexed family of adjunctions with some process category - which unfolds relational structures into tree-like forms, allowing natural resource parameters to be assigned to these unfoldings. One basic instance of this scheme allows us to recover, in a purely structural, syntax-free way: the Ehrenfeucht-Fraïssé game; the quantifier rank fragments of first-order logic; the equivalences on structures induced by (i) the quantifier rank fragments, (ii) the restriction of this fragment to the existential positive part, and (iii) the extension with counting quantifiers; and the combinatorial parameter of tree-depth (Nesetril and Ossona de Mendez). Another instance recovers the k-pebble game, the finite-variable fragments, the corresponding equivalences, and the combinatorial parameter of treewidth. Other instances cover modal, guarded and hybrid fragments, generalized quantifiers, and a wide range of combinatorial parameters. This whole scheme has been axiomatized in a very general setting, of arboreal categories and arboreal covers. Beyond this basic level, a landscape is beginning to emerge, in which structural features of the resource categories, adjunctions and comonads are reflected in degrees of logical and computational tractability of the corresponding languages. Examples include semantic characterisation and preservation theorems, and Lovász-type results on counting homomorphisms. [ABSTRACT FROM AUTHOR]

Nowadays natural language generation (NLG) is used in everything from news reporting and chatbots to social media management. Recent advances in machine learning have made it possible to train NLG systems that seek to achieve human-level performance in text writing and summarisation. In this paper, we propose such a system in the context of Wikipedia and evaluate it with Wikipedia readers and editors. Our solution builds upon the ArticlePlaceholder, a tool used in 14 under-resourced Wikipedia language versions, which displays structured data from the Wikidata knowledge base on empty Wikipedia pages. We train a neural network to generate an introductory sentence from the Wikidata triples shown by the ArticlePlaceholder, and explore how Wikipedia users engage with it. The evaluation, which includes an automatic, a judgement-based, and a task-based component, shows that the summary sentences score well in terms of perceived fluency and appropriateness for Wikipedia, and can help editors bootstrap new articles. It also hints at several potential implications of using NLG solutions in Wikipedia at large, including content quality, trust in technology, and algorithmic transparency. [ABSTRACT FROM AUTHOR]

An operating system kernel uses cryptographically secure pseudorandom number generator (CSPRNG) for creating address space layout randomization (ASLR) offsets to protect memory addresses of processes from exploitation, storing users' passwords securely and creating cryptographic keys. However, at present, popular kernel CSPRNGs such as Yarrow, Fortuna and /dev/(u)random which are used by MacOS/iOS/FreeBSD, Windows and Linux/Android kernels respectively lack the very crucial property of non-reproducibility of their generated bitstreams which is used to nullify the scope of predicting the bitstream. This paper proposes a CSPRNG called Cryptographically Secure Pseudorandom Number Generator for Kernel Applications (KCS-PRNG) which generates non-reproducible bitstreams. The proposed KCS-PRNG presents an efficient design uniquely configured with two new non-standard and verified elliptic curves and clock-controlled Linear Feedback Shift Registers (LFSRs) and a novel method to consistently generate non-reproducible random bitstreams of arbitrary lengths. The generated bitstreams are statistically indistinguishable from true random bitstreams and provably secure, resilient to important attacks, exhibits backward and forward secrecy, exhibits exponential linear complexity, large period and huge key space. [ABSTRACT FROM AUTHOR]

System diagnosis is process of identifying faulty nodes in a system. An efficient diagnosis is crucial for a multiprocessor system. The BGM diagnosis model is a modification of the PMC diagnosis model, which is a test-based diagnosis. In this paper, we present a specific structure and propose an algorithm for diagnosing a node in a system under the BGM model. We also give a polynomial-time algorithm that a node in a hypercube-like network can be diagnosed correctly in three test rounds under the BGM diagnosis model. [ABSTRACT FROM AUTHOR]

The 'mathematical language' Automath, conceived by N.G. de Bruijn in 1968, was the first theorem prover actually working and was used for checking many specimina of mathematical content. Its goals and syntactic ideas inspired Th. Coquand and G. Huet to develop the calculus of constructions, CC ([1]), which was one of the first widely used interactive theorem provers and forms the basis for the widely used Coq system ([2]). The original syntax of Automath ([3, 4]) is not easy to grasp. Yet, it is essentially based on a derivation system that is similar to the Calculus of Constructions ('CC'). The relation between the Automath syntax and CC has not yet been sufficiently described, although there are many references in the type theory community to Automath. In this paper we focus on the backgrounds and on some uncommon aspects of the syntax of Automath. We expose the fundamental aspects of a 'generic' Automath system, encapsulating the most common versions of Automath. We present this generic Automath system in a modern syntactic frame. The obtained system makes use of λD, a direct extension of CC with definitions described in [5]. [ABSTRACT FROM AUTHOR]

The aim of this paper is to obtain closed formulas for the perfect domination number, the Roman domination number and the perfect Roman domination number of lexicographic product graphs. We show that these formulas can be obtained relatively easily for the case of the first two parameters. The picture is quite different when it concerns the perfect Roman domination number. In this case, we obtain general bounds and then we give sufficient and/or necessary conditions for the bounds to be achieved. We also discuss the case of perfect Roman graphs and we characterize the lexicographic product graphs where the perfect Roman domination number equals the Roman domination number. [ABSTRACT FROM AUTHOR]

Two integral quadratic unit forms are called strongly Gram congruent if their upper triangular Gram matrices are ℤ-congruent. The paper gives a combinatorial strong Gram invariant for those unit forms that are non-negative of Dynkin type r (for r ≥ 1), within the framework introduced in [Fundamenta Informaticae 184(1):49–82, 2021], and uses it to determine all corresponding Coxeter polynomials and (reduced) Coxeter numbers. [ABSTRACT FROM AUTHOR]

Domination-type parameters are difficult to manage in Cartesian product graphs and there is usually no general relationship between the parameter in both factors and in the product graph. This is the situation of the domination number, the Roman domination number or the 2-domination number, among others. Contrary to what happens with the domination number and the Roman domination number, the 2-domination number remains unknown in cylinders, that is, the Cartesian product of a cycle and a path and in this paper, we will compute this parameter in the cylinders with small cycles. We will develop two algorithms involving the (min, +) matrix product that will allow us to compute the desired values of γ2(Cn□Pm), with 3 ≤ n ≤ 15 and m ≤ 2. We will also pose a conjecture about the general formula for the 2-domination number in this graph class. [ABSTRACT FROM AUTHOR]

"There and Back Again" (TABA) is a programming pattern where the recursive calls traverse one data structure and the subsequent returns traverse another. This article presents new TABA examples, refines existing ones, and formalizes both their control flow and their data flow using the Coq Proof Assistant. Each formalization mechanizes a pen-and-paper proof, thus making it easier to "get" TABA. In addition, this article identifies and illustrates a tail-recursive variant of TABA, There and Forth Again (TAFA) that does not come back but goes forth instead with more tail calls. [ABSTRACT FROM AUTHOR]

It is known that each word of length n contains at most n + 1 distinct palindromes. A finite rich word is a word with maximal number of palindromic factors. The definition of palindromic richness can be naturally extended to infinite words. Sturmian words and Rote complementary symmetric sequences form two classes of binary rich words, while episturmian words and words coding symmetric d-interval exchange transformations give us other examples on larger alphabets. In this paper we look for morphisms of the free monoid, which allow us to construct new rich words from already known rich words. We focus on morphisms in Class Pret. This class contains morphisms injective on the alphabet and satisfying a particular palindromicity property: for every morphism ϕ in the class there exists a palindrome w such that ϕ(a)w is a first complete return word to w for each letter a. We characterize Pret morphisms which preserve richness over a binary alphabet. We also study marked Pret morphisms acting on alphabets with more letters. In particular we show that every Arnoux-Rauzy morphism is conjugated to a morphism in Class Pret and that it preserves richness. [ABSTRACT FROM AUTHOR]

The popularity of the Semantic Web (SW) encourages organizations to organize and publish semantic data using the RDF model. This growth poses new requirements to Business Intelligence technologies to enable On-Line Analytical Processing (OLAP)-like analysis over semantic data. The incorporation of semantic data into a Data Warehouse (DW) is not supported by the traditional Extract-Transform-Load (ETL) tools because they do not consider semantic issues in the integration process. In this paper, we propose a layer-based integration process and a set of high-level RDF-based ETL constructs required to define, map, extract, process, transform, integrate, update, and load (multidimensional) semantic data. Different to other ETL tools, we automate the ETL data flows by creating metadata at the schema level. Therefore, it relieves ETL developers from the burden of manual mapping at the ETL operation level. We create a prototype, named Semantic ETL Construct (SETLCONSTRUCT), based on the innovative ETL constructs proposed here. To evaluate SETLCONSTRUCT, we create a multidimensional semantic DW by integrating a Danish Business dataset and an EU Subsidy dataset using it and compare it with the previous programmable framework SETLPROG in terms of productivity, development time, and performance. The evaluation shows that 1) SETLCONSTRUCT uses 92% fewer Number of Typed Characters (NOTC) than SETLPROG, and SETLAUTO (the extension of SETLCONSTRUCT for generating ETL execution flows automatically) further reduces the Number of Used Concepts (NOUC) by another 25%; 2) using SETLCONSTRUCT, the development time is almost cut in half compared to SETLPROG, and is cut by another 27% using SETLAUTO; and 3) SETLCONSTRUCT is scalable and has similar performance compared to SETLPROG. We also evaluate our approach qualitatively by interviewing two ETL experts. [ABSTRACT FROM AUTHOR]

This paper presents a new software framework, Sampo-UI, for developing user interfaces for semantic portals. The goal is to provide the end-user with multiple application perspectives to Linked Data knowledge graphs, and a two-step usage cycle based on faceted search combined with ready-to-use tooling for data analysis. For the software developer, the Sampo-UI framework makes it possible to create highly customizable, user-friendly, and responsive user interfaces using current state-of-the-art JavaScript libraries and data from SPARQL endpoints, while saving substantial coding effort. Sampo-UI is published on GitHub under the open MIT License and has been utilized in several internal and external projects. The framework has been used thus far in creating six published and five forth-coming portals, mostly related to the Cultural Heritage domain, that have had tens of thousands of end-users on the Web. [ABSTRACT FROM AUTHOR]

In this paper, we propose an argumentation formalism that allows for both deductive and abductive argumentation, where 'deduction' is used as an umbrella term for both defeasible and strict 'forward' inference. Our formalism is based on an extended version of our previously proposed information graph (IG) formalism, which provides a precise account of the interplay between deductive and abductive inference and causal and evidential information. In the current version, we consider additional types of information such as abstractions which allow domain experts to be more expressive in stating their knowledge, where we identify and impose constraints on the types of inferences that may be performed with the different types of information. A new notion of attack is defined that captures a crucial aspect of abductive reasoning, namely that of competition between abductively inferred alternative explanations. Our argumentation formalism generates an abstract argumentation framework and thus allows arguments to be formally evaluated. We prove that instantiations of our argumentation formalism satisfy key rationality postulates. [ABSTRACT FROM AUTHOR]

In the 1980s, Pollock's work on default reasons started the quest in the AI community for a formal system of defeasible argumentation. The main goal of this paper is to provide a logic of structured defeasible arguments using the language of justification logic. In this logic, we introduce defeasible justification assertions of the type t : F that read as "t is a defeasible reason that justifies F". Such formulas are then interpreted as arguments and their acceptance semantics is given in analogy to Dung's abstract argumentation framework semantics. We show that a large subclass of Dung's frameworks that we call "warranted" frameworks is a special case of our logic in the sense that (1) Dung's frameworks can be obtained from justification logic-based theories by focusing on a single aspect of attacks among justification logic arguments and (2) Dung's warranted frameworks always have multiple justification logic instantiations called "realizations". We first define a new justification logic that relies on operational semantics for default logic. One of the key features that is absent in standard justification logics is the possibility to weigh different epistemic reasons or pieces of evidence that might conflict with one another. To amend this, we develop a semantics for "defeaters": conflicting reasons forming a basis to doubt the original conclusion or to believe an opposite statement. This enables us to formalize non-monotonic justifications that prompt extension revision already for normal default theories. Then we present our logic as a system for abstract argumentation with structured arguments. The format of conflicting reasons overlaps with the idea of attacks between arguments to the extent that it is possible to define all the standard notions of argumentation framework extensions. Using the definitions of extensions, we establish formal correspondence between Dung's original argumentation semantics and our operational semantics for default theories. One of the results shows that the notorious attack cycles from abstract argumentation cannot always be realized as justification logic default theories. [ABSTRACT FROM AUTHOR]

In Quality function deployment (QFD) approach, customers tend to express their needs in linguistic terms rather than exact numerical values and these needs generally contain vague and imprecise information. To overcome this challenge and to use the method more effectively for complex customer-oriented design problems, this paper introduces a novel intuitionistic Z-fuzzy QFD method based on Chebyshev's inequality (CI) and applies it for a new product design. CI provides the assignment of a more objective reliability function. The reliability value is based on the maximum probability obtained from CI. Then, the expected values of lower and upper bounds of interval-valued intuitionistic fuzzy (IVIF) numbers are determined. A competitive analysis among our firm and competitor firms and an integrative analysis for the different functions of QFD is presented. The proposed Z-fuzzy QFD method is applied to the design and development of a hand sanitizer for struggling with COVID-19. [ABSTRACT FROM AUTHOR]

In this paper, a new approach has been proposed for multi-label text data class verification and adjustment. The approach helps to make semi-automated revisions of class assignments to improve the quality of the data. The data quality significantly influences the accuracy of the created models, for example, in classification tasks. It can also be useful for other data analysis tasks. The proposed approach is based on the combination of the usage of the text similarity measure and two methods: latent semantic analysis and self-organizing map. First, the text data must be pre-processed by selecting various filters to clean the data from unnecessary and irrelevant information. Latent semantic analysis has been selected to reduce the vectors dimensionality of the obtained vectors that correspond to each text from the analysed data. The cosine similarity distance has been used to determine which of the multi-label text data class should be changed or adjusted. The self-organizing map has been selected as the key method to detect similarity between text data and make decisions for a new class assignment. The experimental investigation has been performed using the newly collected multi-label text data. Financial news data in the Lithuanian language have been collected from four public websites and classified by experts into ten classes manually. Various parameters of the methods have been analysed, and the influence on the final results has been estimated. The final results are validated by experts. The research proved that the proposed approach could be helpful to verify and adjust multi-label text data classes. 82% of the correct assignments are obtained when the data dimensionality is reduced to 40 using the latent semantic analysis, and the self-organizing map size is reduced from 40 to 5 by step 5. [ABSTRACT FROM AUTHOR]

In order to avoid working in a constrained hazardous environment, manual spray painting operation is gradually being replaced by automated robotic systems in many manufacturing industries. Application of spray painting robots ensures defect-free painting of dissimilar components with higher repeatability, flexibility, productivity, reduced cycle time and minimum wastage of paint. Due to availability of a large number of viable options in the market, selection of a spray painting robot suitable for a given application poses a great problem. Thus, this paper proposes the integrated application of step-wise weight assessment ratio analysis (SWARA) and combined compromise solution (CoCoSo) methods to identify the most apposite spray painting robot for an automobile industry based on seven evaluation criteria (payload, mass, speed, repeatability, reach, cost and power consumption). The SWARA method identifies cost as the most significant criterion based on a set preference order, whereas, Fanuc P-350iA/45 is selected as the best spray painting robot by CoCoSo method. The derived ranking results are also contrasted with other popular multi-criteria decision making (MCDM) techniques (TOPSIS, VIKOR, COPRAS, PROMETHEE and MOORA) and subjective criteria weighting methods (AHP, PIPRECIA, BWM and FUCOM). High degrees of similarity in the ranking patterns between the adopted approach and other MCDM techniques prove its effectiveness in solving complex industrial robot selection problems. This integrated approach is proved to be quite robust being almost unaffected by the changing values of the corresponding tuning parameter in low-dimensional MCDM problems. [ABSTRACT FROM AUTHOR]

This paper aims to develop a Fermatean fuzzy ELECTRE method for solving multi-criteria group decision-making problems with unknown weights of decision makers and incomplete weights of criteria. First, a new distance measure between Fermatean fuzzy sets is proposed based on the Jensen–Shannon divergence. The cross entropy for Fermatean fuzzy sets is defined. Three kinds of dominance relationships for Fermatean fuzzy sets are proposed. Then, two optimization models are constructed to obtain positive ideal decision-making information and negative ideal decision-making information, respectively. Accordingly, the credibility degree of each decision maker is calculated. Decision makers' dynamic weights are determined by their credibility degrees. Besides, to obtain the weights of criteria, an optimization model is constructed based on grey relational analysis for Fermatean fuzzy numbers. Finally, the strong, medium and weak Fermatean fuzzy concordance and discordance sets are identified to construct the Fermatean fuzzy concordance and discordance matrices, respectively. A practical case study is carried out to illustrate the feasibility and applicability of the proposed ELECTRE method. Comparative analyses are performed to demonstrate the superiority and effectiveness of the proposed ELECTRE method. [ABSTRACT FROM AUTHOR]

A proper CNC machine selection problem is an important issue for manufacturing companies under competitive market conditions. The selection of an improper machine tool can cause many problems such as production capabilities and productivity indicators considering time and money industrially and practically. In this paper, a comprehensive solution approach is presented for the CNC machine tool selection problem according to the determined criteria. Seven main and thirteen sub-criteria were determined for the evaluation of the seven alternatives. To purify the selection process from subjectivity, instead of a single decision-maker, the opinions of six different experts on the importance of the criteria were taken and evaluated using the Best-Worst method. According to the evaluations, the order of importance of the main criteria has been determined as cost, productivity, flexibility, and dimensions. After the weighting of the criteria, three different ranking methods (GRA, COPRAS, and MULTIMOORA) were preferred due to the high investment costs of the selected alternatives. The findings obtained by solving the problem of selection of the CNC machine are close to those obtained by past researchers. As a result, using the suggested methodology, effective alternative decision-making solutions are obtained. [ABSTRACT FROM AUTHOR]

The dynamicity of RDF data has motivated the development of solutions for archiving, i.e., the task of storing and querying previous versions of an RDF dataset. Querying the history of a dataset finds applications in data maintenance and analytics. Notwithstanding the value of RDF archiving, the state of the art in this field is under-developed: (i) most existing systems are neither scalable nor easy to use, (ii) there is no standard way to query RDF archives, and (iii) solutions do not exploit the evolution patterns of real RDF data. On these grounds, this paper surveys the existing works in RDF archiving in order to characterize the gap between the state of the art and a fully-fledged solution. It also provides RDFev, a framework to study the dynamicity of RDF data. We use RDFev to study the evolution of YAGO, DBpedia, and Wikidata, three dynamic and prominent datasets on the Semantic Web. These insights set the ground for the sketch of a fully-fledged archiving solution for RDF data. [ABSTRACT FROM AUTHOR]

Finding a good query plan is key to the optimization of query runtime. This holds in particular for cost-based federation engines, which make use of cardinality estimations to achieve this goal. A number of studies compare SPARQL federation engines across different performance metrics, including query runtime, result set completeness and correctness, number of sources selected and number of requests sent. Albeit informative, these metrics are generic and unable to quantify and evaluate the accuracy of the cardinality estimators of cost-based federation engines. To thoroughly evaluate cost-based federation engines, the effect of estimated cardinality errors on the overall query runtime performance must be measured. In this paper, we address this challenge by presenting novel evaluation metrics targeted at a fine-grained benchmarking of cost-based federated SPARQL query engines. We evaluate five cost-based federated SPARQL query engines using existing as well as novel evaluation metrics by using LargeRDFBench queries. Our results provide a detailed analysis of the experimental outcomes that reveal novel insights, useful for the development of future cost-based federated SPARQL query processing engines. [ABSTRACT FROM AUTHOR]

Crystal Structure Prediction (CSP) is one of the central and most challenging problems in materials science and computational chemistry. In CSP, the goal is to find a configuration of ions in 3D space that yields the lowest potential energy. Finding an efficient procedure to solve this complex optimisation question is a well known open problem. Due to the exponentially large search space, the problem has been referred in several materials-science papers as "NP-Hard and very challenging" without a formal proof. This paper fills a gap in the literature providing the first set of formally proven NP-Hardness results for a variant of CSP with various realistic constraints. In particular, we focus on the problem of removal: the goal is to find a substructure with minimal potential energy, by removing a subset of the ions. Our main contributions are NP-Hardness results for the CSP removal problem, new embeddings of combinatorial graph problems into geometrical settings, and a more systematic exploration of the energy function to reveal the complexity of CSP. In a wider context, our results contribute to the analysis of computational problems for weighted graphs embedded into the three-dimensional Euclidean space. [ABSTRACT FROM AUTHOR]

Computed tomography coronary angiography (CTCA) is a non-invasive, powerful image processing technique for assessing coronary artery disease. The aim of the paper is to evaluate the diagnostic role of CTCA using optimal scanning parameters and to investigate the effect of low kilovoltage CTCA on the qualitative and quantitative image parameters and radiation dose in overweight and obese patients. Consolidation of knowledge in medicine and image processing was used to achieve the aim, and performance was evaluated in a clinical setting. Elevated body mass index is one of the factors causing increased radiation dose to patients. This study examined the feasibility of 80-kV and 100-kV CTCA in overweight and obese adult patients, comparing radiation doses and image quality versus standardized 100-kV protocols in the group of overweight patients and 120-kV CTCA in the group of obese patients. Qualitative and quantitative image parameters were determined in proximal and distal segments of the coronary arteries. Quantitative assessment was determined by the contrast-to-noise ratio and signal-to-noise ratio. The results of the study showed that in overweight and obese patients, the low dose protocol affords radiation dose reduction of 35% and 41%, respectively. Image quality was found to be diagnostically acceptable in all cases. [ABSTRACT FROM AUTHOR]

Convolutional neural networks (CNNs) were popular in ImageNet large scale visual recognition competition (ILSVRC 2012) because of their identification ability and computational efficiency. This paper proposes a palm vein recognition method based on CNN. The four main steps of palm vein recognition are image acquisition, image preprocessing, feature extraction, and matching. To reduce the processing steps in the recognition of palm vein images, a palm vein recognition method using a CNN is proposed. CNN is a deep learning network. Palm vein images are acquired using near-infrared light, under which the veins in the palm of the hand are relatively prominent. To obtain a good vein image, many previous methods used preprocessing to further enhance the image before using feature extraction to find feature matches for further comparison. In recent years, CNNs have been shown to have great advantages and have performed well in image classification. To reduce early-stage image processing, a CNN is used to classify and recognize palm vein images. The networks AlexNet and VGG depth CNN were trained to extract image features. The palm vein recognition rates by VGG-19, VGG-16, and AlexNet were 98.5%, 97.5%, and 96%, respectively. [ABSTRACT FROM AUTHOR]

There exist various types of similarity measures for intuitionistic fuzzy sets in the literature. However, in many studies the interactions among the elements are ignored in the construction of the similarity measure. This paper presents a cosine similarity measure for intuitionistic fuzzy sets by using a Choquet integral model in which the interactions between elements are considered. The proposed similarity measure is applied to some pattern recognition problems and the results are compared with some existing results to demonstrate the effectiveness of this new similarity measure. [ABSTRACT FROM AUTHOR]

This paper presents a comprehensive study of argumentation frameworks with necessities (AFNs), a bipolar extension of Dung Abstract argumentation frameworks (AFs) where the support relation captures a positive interaction between arguments having the meaning of necessity: the acceptance of an argument may require the acceptance of other argument(s). The paper discusses new main acceptability semantics for AFNs and their characterization both by a direct approach and a labelling approach. It examines the relationship between AFNs and Dung AFs and shows the gain provided by the former in terms of concision. Finally, the paper shows how to represent an AFN as a normal logic program (LP) and vice versa and in both cases establishes a one-to-one correspondence between extensions under the main acceptability semantics (except for semi-stable semantics where the correspondence is not completely full) of an AFN and particular cases of 3-valued stable models of normal LPs.

This paper presents a study of use of the rhetorical figure of antithesis and other contrastive relations in several modern-day environmental science policy journal articles on issues of food security, climate change, and water resource management. The articles present the conflicting perspectives of environmentalists and engineers, i.e., the view that nature should be preserved and protected versus the view that it should be engineered to solve human problems. The main contribution of this paper is a taxonomy characterizing argumentative uses of contrastive relations in these articles based on our semantic/pragmatic interpretation of text including, in some cases, discourse coherence relations. The number of examples and the breadth of the taxonomy is indicative of the key role of contrastive relations in argumentation in this genre. This investigation is a necessary step towards comprehensive computational approaches to detecting antithesis and other contrastive relations and to identifying their argumentative roles.

Bias in Artificial Intelligence (AI) is a critical and timely issue due to its sociological, economic and legal impact, as decisions made by biased algorithms could lead to unfair treatment of specific individuals or groups. Multiple surveys have emerged to provide a multidisciplinary view of bias or to review bias in specific areas such as social sciences, business research, criminal justice, or data mining. Given the ability of Semantic Web (SW) technologies to support multiple AI systems, we review the extent to which semantics can be a "tool" to address bias in different algorithmic scenarios. We provide an in-depth categorisation and analysis of bias assessment, representation, and mitigation approaches that use SW technologies. We discuss their potential in dealing with issues such as representing disparities of specific demographics or reducing data drifts, sparsity, and missing values. We find research works on AI bias that apply semantics mainly in information retrieval, recommendation and natural language processing applications and argue through multiple use cases that semantics can help deal with technical, sociological, and psychological challenges. [ABSTRACT FROM AUTHOR]

Since the beginning of the release of open data by many countries, different methodologies for publishing linked data have been proposed. However, they seem not to be adopted by early studies exploring linked data for different reasons. In this work, we conducted a systematic mapping in the literature to synthesize the different approaches around the following topics: common steps, associated tools and practices, quality assessment validations, and evaluation of the methodology. The findings show a core set of activities, based on the linked data principles, but with additional critical steps for practical use in scale. Furthermore, although a fair amount of quality issues are reported in the literature, very few of these methodologies embed validation steps in their process. We describe an integrated overview of the different activities and how they can be executed with appropriate tools. We also present research challenges that need to be addressed in future works in this area. [ABSTRACT FROM AUTHOR]

This paper proposes a formal top-level model of explaining the outputs of machine-learning-based decision-making applications and evaluates it experimentally with three data sets. The model draws on AI & law research on argumentation with cases, which models how lawyers draw analogies to past cases and discuss their relevant similarities and differences in terms of relevant factors and dimensions in the problem domain. A case-based approach is natural since the input data of machine-learning applications can be seen as cases. While the approach is motivated by legal decision making, it also applies to other kinds of decision making, such as commercial decisions about loan applications or employee hiring, as long as the outcome is binary and the input conforms to this paper’s factor- or dimension format. The model is top-level in that it can be extended with more refined accounts of similarities and differences between cases. It is shown to overcome several limitations of similar argumentation-based explanation models, which only have binary features and do not represent the tendency of features towards particular outcomes. The results of the experimental evaluation studies indicate that the model may be feasible in practice, but that further development and experimentation is needed to confirm its usefulness as an explanation model. Main challenges here are selecting from a large number of possible explanations, reducing the number of features in the explanations and adding more meaningful information to them. It also remains to be investigated how suitable our approach is for explaining non-linear models.