122,705 research outputs found
Computing Palindromes on a Trie in Linear Time
No full textA trie is a rooted tree such that each edge is labeled by a single character from the alphabet, and the labels of out-going edges from the same node are mutually distinct. Given a trie with n edges, we show how to compute all distinct palindromes and all maximal palindromes on in O(n) time, in the case of integer alphabets of size polynomial in n. This improves the state-of-the-art O(n log h)-time algorithms by Funakoshi et al. [PSC 2019], where h is the height of . Using our new algorithms, the eertree with suffix links for a given trie can readily be obtained in O(n) time. Further, our trie-based O(n)-space data structure allows us to report all distinct palindromes and maximal palindromes in a query string represented in the trie , in output optimal time. This is an improvement over an existing (naïve) solution that precomputes and stores all distinct palindromes and maximal palindromes for each and every string in the trie separately, using a total O(n²) preprocessing time and space, and reports them in output optimal time upon query
Non-Rectangular Convolutions and (Sub-)Cadences with Three Elements
No full textThe discrete acyclic convolution computes the 2n+1 sums ∑_{i+j=k|(i,j)∈[0,1,2,… ,n]²} a_i b_j in ?(n log n) time. By using suitable offsets and setting some of the variables to zero, this method provides a tool to calculate all non-zero sums ∑_{i+j=k|(i,j)∈ P∩ℤ²} a_i b_j in a rectangle P with perimeter p in ?(p log p) time.
This paper extends this geometric interpretation in order to allow arbitrary convex polygons P with k vertices and perimeter p. Also, this extended algorithm only needs ?(k + p(log p)² log k) time.
Additionally, this paper presents fast algorithms for counting sub-cadences and cadences with 3 elements using this extended method
A Multi-Language Comparison of Influences on Author Verification using Character N-Grams
No full textWe create a new multi-language corpus for author verification based on Wikipedia talkpages, and evaluate the influence that differences in topic and time have on character n-gram author profiles. Topic alignment between two texts is found to increase author verification precision, and an authors writing style is found to change over time, but not more significantly after 3 years than after 1 year.Information ArchitectureWISElectrical Engineering, Mathematics and Computer Scienc
Appropriate Similarity Measures for Author Cocitation Analysis
No full textWe 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
The vanishing author in computer-generated works: a critical analysis of recent Australian case law
No full textAbstract
The use of software is ubiquitous in the creation of many copyright works, yet the requirement in copyright law that every work have a human author who engages in independent intellectual effort means that its use may prevent copyright subsistence. Several recent Australian cases have refocused attention on authorship as an essential criterion of copyright subsistence, and these cases suggest that much computer-produced output may be authorless and thus lack copyright protection. This article, the first in a two-part series, analyses how each case deals with the question of authorship of computer-produced works and why the use of software diminishes copyright protection for a significant number of computer-generated works. The article critiques the application of conventional notions of human authorship developed in the pre-computer age to modern productions and suggests alternative approaches to authorship that satisfy both the major objectives of copyright policy and the need to adapt to the computer age. The article argues that, without a broader judicial approach to authorship of computer-generated works, Parliament must remedy the lacuna in protection for these ‘authorless’ works. Possible solutions for reform are suggested. In a forthcoming article, the author comprehensively examines those reform proposals
Princípios Filosóficos e histórico do Karate-Do: conhecimento dos praticantes
No full textTCC (Graduação) - Universidade Federal de Santa Catarina. Centro de Desportos. Curso de Graduação em Educação Física.Este estudo teve como objetivo averiguar as informações absorvidas pelos karate-kas de duas academias de Florianópolis sobre o histórico, os princípios filosóficos e sua aplicabilidade. Participaram do estudo 22 karate-kas de duas academias de Florianópolis/SC, sendo que 20 eram do sexo masculino e dois do sexo feminino, a média de idade dos sujeitos da pesquisa foi de 32,59±9,66 anos; com média de tempo de prática de 7,72±6,35 anos, com a graduação dos karate-kas variando de amarela a preta. Como instrumento de medida utilizou-se um questionário, com questões abertas, testadas cientificamente, obtendo um índice de validação de 91,37%. Os dados foram trabalhados mediante a estatística descritiva em termos de frequência simples, bem como a estatística inferencial, com teste não-parametrico Qui-Quadrado, com probabilidade de 0,05. Os resultados mostram que com relação aos conhecimentos básicos do histórico do Karate-Do metade dos praticantes apresentaram conhecimento, já sobre um conhecimento mais relevante menos da metade apresentou algum conhecimento; quanto aos princípios filosóficos menos da metade dos entrevistados apresentou um pouco conhecimento. Poucos sabiam os mandamentos do dojo e a maioria relatou que o Karate-Do influencia no seu cotidiano. Pode-se concluir que há necessidade de serem abordados os princípios filosóficos do Karate-Do durante as aulas, haja vista os benefícios diretos e indiretos à vida dos praticantes
Diffusive author(s), cohesive author: Analysis of S/N (1994)
No full textThis study indicates the ways in which various aspects of the author(s) are brought forth in Dumb type’s performance art, the S/N production. Previous research has suggested a non-hierarchical organization of Dumb type and the absence of a “privileged author” in Dumb type’s collaborative work, S/N. However, the results that I have investigated from member’s interviews on the creative process of S/N along with my analysis of the recorded images of S/N, indicate a different aspect of the author(s). First, S/N was created through, so to speak, the collective ideas of the members of Dumb type. Further, S/N has at least nine quotations from previous performances, installations, and printed writings, besides the work-in-progress technique. Explicating one of the “author functions” as given by Michel Foucault, each text has plural subjects of the author. However, it has been revealed from members’ interviews that Teiji Furuhashi had a decision-making role in selecting the members’ ideas within the performance. Since then, S/N has had plural subjects of creation; however, Furuhashi is one of the subjects of creation along with the “privileged author.” S/N has plural authors (diffusive authors) yet at the same time, it has a “privileged author,” Teiji Furuhashi (cohesive author)
The Neurospora Peptide:N-Glycanase Ortholog PNG1 Is Essential for Cell Polarity despite Its Lack of Enzymatic Activity
No full textSecretory proteins are subjected to a stringent endoplasmic reticulum-based quality control system that distinguishes aberrant from correctly folded proteins. The cytoplasmic peptide: N-glycanase cleaves oligosaccharides from misfolded glycoproteins and prepares them for degradation by the 26 S proteasome. In contrast to abundant in vitro data on its enzymatic function, the in vivo relevance of peptide: N-glycanase activity remains unclear. Here we show that the PNG1 ortholog from the filamentous ascomycete Neurospora crassa is an essential protein, and its deletion results in strong polarity defects. PNG1 and its predicted binding partner RAD23 have distinct functions in N. crassa and are involved in cell wall integrity and DNA repair, respectively. Moreover, wild type PNG1 has substitutions in essential catalytic amino acids, and its deglycosylation activity is lost. These substitutions are conserved in many PNG1 orthologs of the fungal kingdom, implying a so far unrecognized enzyme-independent function of PNG1 that may only become apparent in highly polar cells such as fungal hyphae
Longest substring palindrome after edit
No full textIt is known that the length of the longest substring palindromes (LSPals) of a given string T of length n can be computed in O(n) time by Manacher's algorithm [J. ACM '75]. In this paper, we consider the problem of finding the LSPal after the string is edited. We present an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(log (min {sigma, log n })) time after single character substitution, insertion, or deletion, where sigma denotes the number of distinct characters appearing in T. We also propose an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(l + log n) time, after an existing substring in T is replaced by a string of arbitrary length l
Faster Queries for Longest Substring Palindrome After Block Edit
No full textPalindromes are important objects in strings which have been extensively studied from combinatorial, algorithmic, and bioinformatics points of views. Manacher [J. ACM 1975] proposed a seminal algorithm that computes the longest substring palindromes (LSPals) of a given string in O(n) time, where n is the length of the string. In this paper, we consider the problem of finding the LSPal after the string is edited. We present an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(l + log log n) time, after a substring in T is replaced by a string of arbitrary length l. This outperforms the query algorithm proposed in our previous work [CPM 2018] that uses O(l + log n) time for each query
- …
