1,720,977 research outputs found
Verification and synthesis of distributed systems with weak synchronisation
No full textLes programmes distribués sont une source de difficulté pour les méthodes formelles. Les interactions de plusieurs composantes provoquent une explosion combinatoire qui complexifie la vérification. Dans le cadre de la synthèse de contrôleurs, à cela s'ajoute le fait que les stratégies d'une composante ne peuvent tenir compte que d'une vision partielle du système. Ceci a mené à de nombreux résultats d'indécidabilité dans le domaine et des complexités très élevées dans les cas décidables. Dans cette thèse, nous proposons une approche permettant de décomposer les problèmes de vérification et de synthèse en instances locales aux processus. Cette approche mène à des résultats de décidabilité, et même dans certains cas à des algorithmes de complexités suffisamment basses pour envisager des applications. Nous montrons que cette méthode s'applique dans des systèmes distribués avec une communication restreinte entre les composantes: d'une part des systèmes où la communication se fait via la prise et le relâchement de locks, et d'autre part des systèmes où les processus communiquent par broadcast. De plus, nous utilisons cette approche dans des modèles a priori très différents, où le nombre de processus est constant, évolue dynamiquement, ou encore est paramétré.Distributed programs are a cause of difficulty for formal methods. The interactions of multiple components lead to a combinatorial explosion, which complicates verification. In the context of controller synthesis, this is further compounded by the fact that the strategies of one component can only take into account a partial view of the system. This has led to numerous undecidability results in the field and very high complexities in decidable cases. In this thesis, we propose an approach that allows the decomposition of verification and synthesis problems into local instances for individual processes. This approach leads to decidability results, and in some cases, to algorithms with low enough complexity to consider practical applications. We show that this method applies to distributed systems with restricted communication between components: on the one hand, systems where communication is limited to the acquisition and release of locks, and on the other hand, systems where processes communicate via broadcast. Moreover, we apply this approach to models that are quite different, where the number of processes is constant, evolves dynamically, or is parameterised
Vérification et synthèse de systèmes distribués à synchronisation faible
No full textDistributed programs are a cause of difficulty for formal methods. The interactions of multiple components lead to a combinatorial explosion, which complicates verification. In the context of controller synthesis, this is further compounded by the fact that the strategies of one component can only take into account a partial view of the system. This has led to numerous undecidability results in the field and very high complexities in decidable cases. In this thesis, we propose an approach that allows the decomposition of verification and synthesis problems into local instances for individual processes. This approach leads to decidability results, and in some cases, to algorithms with low enough complexity to consider practical applications. We show that this method applies to distributed systems with restricted communication between components: on the one hand, systems where communication is limited to the acquisition and release of locks, and on the other hand, systems where processes communicate via broadcast. Moreover, we apply this approach to models that are quite different, where the number of processes is constant, evolves dynamically, or is parameterised.Les programmes distribués sont une source de difficulté pour les méthodes formelles. Les interactions de plusieurs composantes provoquent une explosion combinatoire qui complexifie la vérification. Dans le cadre de la synthèse de contrôleurs, à cela s'ajoute le fait que les stratégies d'une composante ne peuvent tenir compte que d'une vision partielle du système. Ceci a mené à de nombreux résultats d'indécidabilité dans le domaine et des complexités très élevées dans les cas décidables. Dans cette thèse, nous proposons une approche permettant de décomposer les problèmes de vérification et de synthèse en instances locales aux processus. Cette approche mène à des résultats de décidabilité, et même dans certains cas à des algorithmes de complexités suffisamment basses pour envisager des applications. Nous montrons que cette méthode s'applique dans des systèmes distribués avec une communication restreinte entre les composantes: d'une part des systèmes où la communication se fait via la prise et le relâchement de locks, et d'autre part des systèmes où les processus communiquent par broadcast. De plus, nous utilisons cette approche dans des modèles a priori très différents, où le nombre de processus est constant, évolue dynamiquement, ou encore est paramétré
The Complexity of Simplifying -Automata through the Alternating Cycle Decomposition
Full text linkIn 2021, Casares, Colcombet and Fijalkow introduced the Alternating Cycle Decomposition (ACD), a structure used to define optimal transformations of Muller into parity automata and to obtain theoretical results about the possibility of relabelling automata with different acceptance conditions. In this work, we study the complexity of computing the ACD and its DAG-version, proving that this can be done in polynomial time for suitable representations of the acceptance condition of the Muller automaton. As corollaries, we obtain that we can decide typeness of Muller automata in polynomial time, as well as the parity index of the languages they recognise.
Furthermore, we show that we can minimise in polynomial time the number of colours (resp. Rabin pairs) defining a Muller (resp. Rabin) acceptance condition, but that these problems become NP-complete when taking into account the structure of an automaton using such a condition.Full version of a paper accepted at MFCS 2024. v2: Results updated to apply to both automata with single and multiple colours per transitio
On nonnegative integer matrices and short killing words
Full text linkLet n be a natural number, and let \scrM be a set of n\times n-matrices over the nonnegative integers such that the joint spectral radius of \scrM is at most one. We show that if the zero matrix 0 is a product of matrices in \scrM , then there are M1, . . . , Mn5 \in \scrM with M1 \cdot \cdot \cdot Mn5 = 0. This result has applications in automata theory and the theory of codes. Specifically, if X \subset \Sigma \ast is a finite incomplete code, then there exists a word w \in \Sigma \ast of length polynomial in \sum x\in X | x| such that w is not a factor of any word in X\ast . This proves a weak version of Restivo's conjecture
The Complexity of Simplifying ω-Automata Through the Alternating Cycle Decomposition
Full text linkIn 2021, Casares, Colcombet and Fijalkow introduced the Alternating Cycle Decomposition (ACD), a structure used to define optimal transformations of Muller into parity automata and to obtain theoretical results about the possibility of relabelling automata with different acceptance conditions. In this work, we study the complexity of computing the ACD and its DAG-version, proving that this can be done in polynomial time for suitable representations of the acceptance condition of the Muller automaton. As corollaries, we obtain that we can decide typeness of Muller automata in polynomial time, as well as the parity index of the languages they recognise.
Furthermore, we show that we can minimise in polynomial time the number of colours (resp. Rabin pairs) defining a Muller (resp. Rabin) acceptance condition, but that these problems become NP-complete when taking into account the structure of an automaton using such a condition
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
Dispelling the Myths Behind First-author Citation Counts
Full text linkWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
- …
