1,721,003 research outputs found
Proceedings of the 24th Italian Conference on Theoretical Computer Science, Palermo, Italy, September 13-15, 2023
No full text
Algorithmic View on Circular String Attractors
Full text linkThe notion of circular string attractor has been recently introduced by Mantaci et al. [TCS 2021]. It
consists of a set Γc of positions in a word such that each distinct circular factor has at least an occurrence
crossing one of the elements of Γc. Its definition is an extension of the notion of string attractor by Kempa
and Prezza [STOC 2018], which has been introduced as a unifying framework for some dictionary-based
compressors. In this paper, we present the first linear time algorithm to check whether a set is a circular string
attractor of a word w ∈ {a1, . . . , aσ}n by using O(n log n) bits of space. We further show that, for
each p > 0, the decision problem of having a circular string attractor of size ≤ p is NP-complete. The
proof is obtained through a reduction from the analogous problem for string attractors, for which Kempa
and Prezza [STOC 2018] proved the NP-completeness. This reduction naturally leads to a new algorithm
for checking whether a set is a string attractor that, unlike one of the solutions proposed by Kempa et al.
[ESA 2018], it is independent from the size of the alphabet
Assembling Coherent Network Topologies Using Round-Trip Graphs (short paper)
Full text linkDiscovering the network topology in computer networks is challenging due to limited communication and incomplete information about non-immediately connected nodes. In this paper we address the problem of assembling partial views obtained by discovery tools into a coherent representation, using round-trip graphs: labelled bipartite directed graphs representing the communications between hosts, interfaces, and networks. A merge operation is introduced, facilitating compositional and incremental assembly of partial views. This research provides a practical solution for incrementally constructing a comprehensive network topology
A Linear-size Cascade Decomposition for Wheeler Automata
Full text linkThe Krohn-Rhodes Decomposition Theorem (KRDT) is a central result in automata and semigroup theories: it states that any (deterministic) finite-state automaton can be disassembled into a collection of automata of two simple types, that can be arranged into a combination - cascade - that simulates the original automaton. The elementary building blocks of the decomposition are either resets or permutations. The full-fledged theorem features two orthogonal dimensions of complexity: the type and the number of building blocks appearing in the cascade, and a deep step in the proof is the characterization of the permutations appearing in the decomposition. This characterization implies, in the case of counter-free automata, that the resulting cascade contains no permutations. In this paper we start analysing KRDT for two compression-oriented classes of automata: (i) path- coherent: state-ordered automata mapping state-intervals to state-intervals; (ii) Wheeler: a subclass of path-coherent automata whose order is the one induced by the co-lexicographic order of words. These classes were recently defined and studied and they turn out to be efficiently encodable and indexable. We prove that each automata in these classes can be decomposed as a cascade with a number of components which is linear in the number of states of the original automaton and, for the Wheeler class, we prove that only two-state resets are needed. Our line of reasoning avoids the necessity of using full KRDT and proves our results directly by a simple inductive argument
Linear Realisability Over Nets and Second Order Quantification
Full text linkWe present a new realisability model based on othogonality
for Linear Logic in the context of nets – untyped proof structures with
generalized axiom. We show that it adequately models second order multiplicative
linear logic.
As usual, not all realizers are representations of a proof, but we identify
specific types (sets of nets closed under bi-othogonality) that capture
exactly the proofs of a given sequent. Furthermore these types are orthogonal’s
of finite sets; this ensures the existence of a correctnesss criterion
that runs in finite time.
In particular, in the well known case of multiplicative linear logic, the
types capturing the proofs are generated by the tests of Danos-Regnier,
we provide - to our knowledge - the first proof of the folklore result which
states ”test of a formula are proofs of its negation”
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
