112,365 research outputs found
ON THE DESCRIPTIONAL COMPLEXITY OF ACCEPTING NETWORKS OF EVOLUTIONARY PROCESSORS WITH FILTERED CONNECTIONS
No full textIn this paper we consider, from the descriptional complexity point of view, a model of computation introduced in [1], namely accepting network of evolutionary processors with filtered connections (ANEPFCs). First we show that for each morphism h : V → W , with V ∩ W = ∅, one can effectively construct an ANEPFC, of size 6
Rapport V.14. Recherches sur le problème de la rectification du coude du Bras Tulcea
No full textThe straightening of the Tulcea bend in the Danube Delta is a large-scale operation which requires special investigations on site, model tests, hydraulic design calculations and the analysis of a substantial mass of hydrological data. The overall hydraulic research done for the bend-straightening scheme and its conclusions are described from which the layout and cross-section of the new canal and schemes for the construction work required at the canal ends wereLa rectification du coude Tulcea, qui est un secteur du delta du Danube, constitue un travail de grande envergure qui exige des études spéciales in situ, des recherches sur modèle, des calculs hydrauliques et l’analyse d’un grand nombre de données hydrologiques.
Les auteurs présentent l’ensemble des recherches hydrauliques entreprises en vue de l’élaboration du projet de rectification du coude et les conclusions qui ont permis de déterminer le tracé et la section du canal de rectification, ainsi que les schémas des constructions nécessaires aux extrémités du canal.Spataru A., Manea S., Petrescu V. Rapport V.14. Recherches sur le problème de la rectification du coude du Bras Tulcea. In: La prévision des crues et la protection contre les inondations. Dixièmes journées de l'hydraulique. Paris, 5, 6 et 7 juin 1968. Tome 5, 1969
Complexity-preserving simulations among three variants of accepting networks of evolutionary processors
No full textIn this paper we consider three variants of accepting networks of evolutionary processors. It is known that two of them are equivalent to Turing machines. We propose here a direct simulation of one device by the other. Each computational step in one model is simulated in a constant number of computational steps in the other one while a translation via Turing machines squares the time complexity. We also discuss the possibility of constructing simulations that preserve not only complexity, but also the shape of the simulated network. © 2011 Springer Science+Business Media B.V.This work was supported by the Academy of Finland, projects 132727, 122426, and 108421. F. Manea acknowledges the support from the Alexander von Humboldt Foundation. J Sempere acknowledges the support from the Spanish Ministerio de Educacion y Ciencia project TIN2007-60769.Bottoni ., P.; Labella ., A.; Manea ., F.; Mitrana, V.; Petre ., I.; Sempere Luna, JM. (2011). Complexity-preserving simulations among three variants of accepting networks of evolutionary processors. Natural Computing. 10(1):429-445. https://doi.org/10.1007/s11047-010-9238-5S429445101Alhazov A, Bel Enguix G, Rogozhin Y (2009a) Obligatory hybridnetworks of evolutionary processors. In: International conference on agents and artificial intelligence (ICAART 2009), pp 613–618Alhazov A, Csuhaj-Varj E, Martn-Vide C, Rogozhin Y (2009b) On the size of computationally complete hybrid networks ofevolutionaryprocessors. Theor Comput Sci 410:3188–3197Bottoni P, Labella A, Manea F, Mitrana V, Sempere J (2009a) Filter position in networks of evolutionary processors does not matter: a direct proof. In: Proc. 15th international meeting on DNA computing and molecular programming. 8–11 June 2009, Fayetteville, ArkansasBottoni P, Labella A, Mitrana V, Sempere JM (2009b) Networks of evolutionary picture processors with filtered connections. In: Unconventional computation, 8th international conference (UC 2009), LNCS, vol 5715. Springer, Heidelberg, pp 70–84Castellanos J, Martín-Vide C, Mitrana V, Sempere J (2001) Solving NP-complete problems with networks of evolutionary processors. In: International work-conference on artificial and natural neural networks (IWANN 2001), Lecture notes in computer science, vol 2084, pp 621–628Csuhaj-Varjú E, Mitrana V (2000) Evolutionary systems: a language generating device inspired by evolving communities of cells. Acta Inform 36:913–926Csuhaj-Varjú E, Salomaa A (1997) Networks of parallel language processors. In: New trends in formal languages, Lecture notes in computer science, vol 1218, pp 299–318Dassow J, Truthe B (2007) On the power of networks of evolutionary processors. In: Machines, computations, and universality (MCU 2007), Lecture notes in computer science, vol 4667, pp 158–169Drăgoi C, Manea F (2008) On the descriptional complexity of accepting networks of evolutionary processors with filtered connections. Int J Found Comput Sci 19:1113–1132Drăgoi C, Manea F, Mitrana V (2007) Accepting networks of evolutionary processors with filtered connections. J Univers Comput Sci 13:1598–1614Errico L, Jesshope C (1994) Towards a new architecture for symbolic processing. In: Artificial intelligence and information-control systems of robots ’94, World Scientific, Singapore, pp 31–40Fahlman SE, Hinton GE, Seijnowski TJ (1983) Massively parallel architectures for AI: NETL, THISTLE and Boltzmann machines. In: Proc. of the national conference on artificial intelligence, pp 109–113Hillis W (1985) The connection machine. MIT Press, CambridgeManea F, Martin-Vide C, Mitrana V (2007) On the size complexity of universal accepting hybrid networks of evolutionary processors. Math Struct Comput Sci 17:753–771Margenstern M, Mitrana V, Perez-Jimenez M (2005) Accepting hybrid networks of evolutionary systems. In: DNA based computers 10, Lecture notes in computer science, vol, pp 235–246Martín-Vide C, Mitrana V (2005) Networks of evolutionary processors: results and perspectives. In: Molecular computational models: unconventional approaches. dea Group Publishing, Hershey, pp 78–114Păun G (2000) Computing with membranes. J Comput Syst Sci 61:108–143Păun G, Sântean L (1989) Parallel communicating grammar systems: the regular case. Ann Univ Bucharest Ser Matematica Inform 38:55–63Rozenberg G, Salomaa A (eds) (1997) Handbook of formal languages. Springer–Verlag, BerlinSankoff D et al. (1992) Gene order comparisons for phylogenetic inference: evolution of the mitochondrial genome. Proc Natl Acad Sci USA 89:6575–657
Longest Gapped Repeats and Palindromes
No full textA gapped repeat (respectively, palindrome) occurring in a word is a
factor (respectively, ) of . In such a repeat (palindrome)
is called the arm of the repeat (respectively, palindrome), while is called
the gap. We show how to compute efficiently, for every position of the word
, the longest gapped repeat and palindrome occurring at that position,
provided that the length of the gap is subject to various types of
restrictions. That is, that for each position we compute the longest prefix
of such that (respectively, ) is a suffix of
(defining thus a gapped repeat -- respectively, palindrome
), and the length of is subject to the aforementioned restrictions
author-bios-SRD-19-0063.R1 – Supplemental material for The Network Structure of Police Misconduct
No full textSupplemental material, author-bios-SRD-19-0063.R1 for The Network Structure of Police Misconduct by George Wood, Daria Roithmayr and Andrew V. Papachristos in Socius</p
Going Beyond Counting First Authors in Author Co-citation Analysis
No full textThe 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
Subsequences with Generalised Gap Constraints: Upper and Lower Complexity Bounds
No full textFor two strings u, v over some alphabet A, we investigate the problem of embedding u into w as a subsequence under the presence of generalised gap constraints. A generalised gap constraint is a triple (i, j, C_{i, j}), where 1 ≤ i < j ≤ |u| and C_{i, j} ⊆ A^*. Embedding u as a subsequence into v such that (i, j, C_{i, j}) is satisfied means that if u[i] and u[j] are mapped to v[k] and v[], respectively, then the induced gap v[k + 1.. - 1] must be a string from C_{i, j}. This generalises the setting recently investigated in [Day et al., ISAAC 2022], where only gap constraints of the form C_{i, i + 1} are considered, as well as the setting from [Kosche et al., RP 2022], where only gap constraints of the form C_{1, |u|} are considered.
We show that subsequence matching under generalised gap constraints is NP-hard, and we complement this general lower bound with a thorough (parameterised) complexity analysis. Moreover, we identify several efficiently solvable subclasses that result from restricting the interval structure induced by the generalised gap constraints
Variations on the Author
No full text“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
Two complementary operations inspired by the DNA hairpin formation: Completion and reduction
No full textAbstractWe consider two complementary operations: Hairpin completion introduced in [D. Cheptea, C. Martin-Vide, V. Mitrana, A new operation on words suggested by DNA biochemistry: Hairpin completion, in: Proc. Transgressive Computing, 2006, pp. 216–228] with motivations coming from DNA biochemistry and hairpin reduction as the inverse operation of the hairpin completion. Both operations are viewed here as formal operations on words and languages. We settle the closure properties of the classes of regular and linear context-free languages under hairpin completion in comparison with hairpin reduction. While the class of linear context-free languages is exactly the weak-code image of the class of the hairpin completion of regular languages, rather surprisingly, the weak-code image of the class of the hairpin completion of linear context-free languages is a class of mildly context-sensitive languages. The closure properties with respect to the hairpin reduction of some time and space complexity classes are also studied. We show that the factors found in the general cases are not necessary for regular and context-free languages. This part of the paper completes the results given in the earlier paper, where a similar investigation was made for hairpin completion. Finally, we briefly discuss the iterated variants of these operations
- …
