1,721,124 research outputs found
Making Concurrency Functional
Full text linkThe article bridges between two major paradigms in computation, the
functional, at basis computation from input to output, and the interactive,
where computation reacts to its environment while underway. Central to any
compositional theory of interaction is the dichotomy between a system and its
environment. Concurrent games and strategies address the dichotomy in fine
detail, very locally, in a distributed fashion, through distinctions between
Player moves (events of the system) and Opponent moves (those of the
environment). A functional approach has to handle the dichotomy much more
ingeniously, through its blunter distinction between input and output. This has
led to a variety of functional approaches, specialised to particular
interactive demands. Through concurrent games we can more clearly see what
separates and connects the differing paradigms, and show how:
* to lift functions to strategies; the "Scott order" intrinsic to concurrent
games plays a key role in turning functional dependency to causal dependency.
* several paradigms of functional programming and logic arise naturally as
subcategories of concurrent games, including stable domain theory;
nondeterministic dataflow; geometry of interaction; the dialectica
interpretation; lenses and optics; and their extensions to containers in
dependent lenses and optics.
* to transfer enrichments of strategies (such as to probabilistic, quantum or
real-number computation) to functional cases
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
On the Expressive Power of Read-Once Determinants
No full textWe introduce and study the notion of read-k projections of the determinant: a polynomial f∈F[x1,…,xn] is called a read-k projection of determinant if f=det(M), where entries of matrix M are either field elements or variables such that each variable appears at most k times in M. A monomial set S is said to be expressible as read-k projection of determinant if there is a read-k projection of determinant f such that the monomial set of f is equal to S. We obtain basic results relating read-k determinantal projections to the well-studied notion of determinantal complexity. We show that for sufficiently large n, the n×n permanent polynomial Permn and the elementary symmetric polynomials of degree d on n variables Sdn for 2≤d≤n−2 are not expressible as read-once projection of determinant, whereas mon(Permn) and mon(Sdn) are expressible as read-once projections of determinant. We also give examples of monomial sets which are not expressible as read-once projections of determinant
Constructive Relationships Between Algebraic Thickness and Normality
No full textWe study the relationship between two measures of Boolean functions; algebraic thickness and normality. For a function f, the algebraic thickness is a variant of the sparsity, the number of nonzero coefficients in the unique F2 polynomial representing f, and the normality is the largest dimension of an affine subspace on which f is constant. We show that for 0<ϵ<2 , any function with algebraic thickness n3−ϵ is constant on some affine subspace of dimension Ω(nϵ/2) . Furthermore, we give an algorithm for finding such a subspace. We show that this is at most a factor of Θ(√n) from the best guaranteed, and when restricted to the technique used, is at most a factor of Θ(√log n) from the best guaranteed. We also show that a concrete function, majority, has algebraic thickness Ω(2n1/6)
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
Unfolding based verification of concurrent infinite-state systems
No full textNous proposons une technique de dépliage pour vérifier les systèmes concurrents infinis bien structurés. Certaines propriétés d'intérêt comme la bornitude, la couverture et la terminaison sont décidables grâce à la bonne structure de ces systèmes. D'autre part, le dépliage réduit efficacement l'explosion combinatoire en exploitant l'ordre partiel entre les événements des systèmes concurrents. Nous proposons une modélisation par structure d'événements pour des systèmes bien structurés élémentaires, tels les compteurs et les files de communication. Le dépliage d'un réseau de structures d'événements étant une structure d'événements, nous proposons ensuite une approche hiérarchique à la modélisation et à la vérification des systèmes, qui préserve la bonne structure. Enfin, nous proposons une technique d'élimination des événements redondants. La mise en œuvre de notre approche dans l'outil ESU nous permet de conclure à son efficacité.We propose an unfolding technique for verifying concurrent infinite-state systems that are well-structured. Some properties of interest such as boundedness, coverability and termination are decidable thanks to the well-structure of these systems. Moreover, the unfolding effectively reduces the combinatorial explosion by exploiting the partial order between events of concurrent systems. We propose a modelization using event structures for basic well-structured systems, such as counters and communication channels. As the unfolding of a synchronized product of event structures is an event structure, we obtain a hierarchical approach to modeling as well as to verifying systems, which preserves the well-structure. Finally, we propose a technique for eliminating redundant events. The implementation of our approach in the ESU tool allows us to conclude on its efficiency
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
Structural properties of automata over infinite words and memory for games
No full textLes automates et les jeux à durée infinie constituent l’un des outils fondamentaux pour la vérification et la synthèse de systèmes réactifs. Contrairement au cas des langages réguliers sur les mots finis, plusieurs modèles d’automates existent, et de nombreuses questions sur leur structure et sur les langages qu’ils reconnaissent restent ouvertes. Dans cette thèse, nous étudions des transformations entre différents types d'automates sur les mots infinis, le problème de la minimisation, et le lien entre la structure de ces automates et la complexité des stratégies nécessaires pour gagner des jeux sur des graphes avec condition de gain omega-régulière.Automata and infinite duration games form the theoretical basis for the verification and synthesis of reactive systems. Contrary to the case of regular languages over finite words, several models of omega-automata exist, each one offering its own advantages. However, their structural and language-theoretical properties are still far from being fully understood. In this thesis, we study transformations between different types of omega-automata, as well as the minimisation problem. Moreover, we exhibit links between these automata and the complexity of winning strategies for games with omega-regular winning conditions, giving a complete characterisation of half-positionality for omega-regular languages
- …
