Search results for " set"
showing 10 items of 2095 documents
A Classification of Trapezoidal Words
2011
Trapezoidal words are finite words having at most n+1 distinct factors of length n, for every n>=0. They encompass finite Sturmian words. We distinguish trapezoidal words into two disjoint subsets: open and closed trapezoidal words. A trapezoidal word is closed if its longest repeated prefix has exactly two occurrences in the word, the second one being a suffix of the word. Otherwise it is open. We show that open trapezoidal words are all primitive and that closed trapezoidal words are all Sturmian. We then show that trapezoidal palindromes are closed (and therefore Sturmian). This allows us to characterize the special factors of Sturmian palindromes. We end with several open problems.
Sparsity-Driven Digital Terrain Model Extraction
2020
We here introduce an automatic Digital Terrain Model (DTM) extraction method. The proposed sparsity-driven DTM extractor (SD-DTM) takes a high-resolution Digital Surface Model (DSM) as an input and constructs a high-resolution DTM using the variational framework. To obtain an accurate DTM, an iterative approach is proposed for the minimization of the target variational cost function. Accuracy of the SD-DTM is shown in a real-world DSM data set. We show the efficiency and effectiveness of the approach both visually and quantitatively via residual plots in illustrative terrain types.
The Inconsistent Labelling Problem of Stutter-Preserving Partial-Order Reduction
2020
AbstractIn model checking, partial-order reduction (POR) is an effective technique to reduce the size of the state space. Stubborn sets are an established variant of POR and have seen many applications over the past 31 years. One of the early works on stubborn sets shows that a combination of several conditions on the reduction is sufficient to preserve stutter-trace equivalence, making stubborn sets suitable for model checking of linear-time properties. In this paper, we identify a flaw in the reasoning and show with a counter-example that stutter-trace equivalence is not necessarily preserved. We propose a solution together with an updated correctness proof. Furthermore, we analyse in whi…
RIGA at SemEval-2016 Task 8: Impact of Smatch Extensions and Character-Level Neural Translation on AMR Parsing Accuracy
2016
Two extensions to the AMR smatch scoring script are presented. The first extension com-bines the smatch scoring script with the C6.0 rule-based classifier to produce a human-readable report on the error patterns frequency observed in the scored AMR graphs. This first extension results in 4% gain over the state-of-art CAMR baseline parser by adding to it a manually crafted wrapper fixing the identified CAMR parser errors. The second extension combines a per-sentence smatch with an en-semble method for selecting the best AMR graph among the set of AMR graphs for the same sentence. This second modification au-tomatically yields further 0.4% gain when ap-plied to outputs of two nondeterministic…
Primitive sets of words
2020
Given a (finite or infinite) subset $X$ of the free monoid $A^*$ over a finite alphabet $A$, the rank of $X$ is the minimal cardinality of a set $F$ such that $X \subseteq F^*$. We say that a submonoid $M$ generated by $k$ elements of $A^*$ is {\em $k$-maximal} if there does not exist another submonoid generated by at most $k$ words containing $M$. We call a set $X \subseteq A^*$ {\em primitive} if it is the basis of a $|X|$-maximal submonoid. This definition encompasses the notion of primitive word -- in fact, $\{w\}$ is a primitive set if and only if $w$ is a primitive word. By definition, for any set $X$, there exists a primitive set $Y$ such that $X \subseteq Y^*$. We therefore call $Y$…
Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees
2017
International audience; The search of spanning trees with interesting disjunction properties has led to the introduction of edge-disjoint spanning trees, independent spanning trees and more recently completely independent spanning trees. We group together these notions by dening (i, j)-disjoint spanning trees, where i (j, respectively) is the number of vertices (edges, respectively) that are shared by more than one tree. We illustrate how (i, j)-disjoint spanning trees provide some nuances between the existence of disjoint connected dominating sets and completely independent spanning trees. We prove that determining if there exist two (i, j)-disjoint spanning trees in a graph G is NP-comple…
Molecular equilibrium structures from experimental rotational constants and calculated vibration–rotation interaction constants
2002
A detailed study is carried out of the accuracy of molecular equilibrium geometries obtained from least-squares fits involving experimental rotational constants B(0) and sums of ab initio vibration-rotation interaction constants alpha(r)(B). The vibration-rotation interaction constants have been calculated for 18 single-configuration dominated molecules containing hydrogen and first-row atoms at various standard levels of ab initio theory. Comparisons with the experimental data and tests for the internal consistency of the calculations show that the equilibrium structures generated using Hartree-Fock vibration-rotation interaction constants have an accuracy similar to that obtained by a dir…
Dépôts carbonatés microbiens en domaine lacustre et fluviatile : fabriques et facteurs de contrôle
2020
The non-marine carbonates related to microbial activity display a large range of morphologies and compositions and accumulate in various settings (freshwater, alkaline, and saline lakes, fluvial environments, thermal and freshwater springs, …). The variety of non-marine microbial carbonates and their particularity led to propose numerous and complex terminologies and classifications, making their use complicated and restrictive for the interpretation of depositional settings. Mineralization of these carbonates results from the interaction between biotic factors (intrinsic) and environmental factors (extrinsic and external) at multi-scales. The first aim of this work was to characterize morp…
Facebook’s ad hoc groups: a potential source of communicative power of networked citizens
2017
Ad hoc groups (sporadically formed on social network sites for achieving particular common objectives) have been seen as a public space for citizen participation and debate. This study focuses on Facebook’s ad hoc groups in Finland. The aim is to detect the potential of these groups to enhance networked citizens’ communicative power for raising societally important issues to public agenda and initiate changes in society. We suggest a categorization of the groups according to their missions, and present their members’ specific motivations and objectives through an online survey. Despite the general entertainment-orientation and self-referential nature of social media, the results show that a…
TREEZZY2, a Fuzzy Logic Computer Code for Fault Tree and Event Tree Analyses
2004
In conventional approach to reliability analysis using logical trees methodologies, uncertainties in system components or basic events failure probabilities are approached by assuming probability distribution functions. However, data are often insufficient for statistical estimation, and therefore it is required to resort to approximate estimations. Moreover, complicate calculations are needed to propagate uncertainties up to the final results. In our work, in order to take account of the uncertainties in system failure probabilities, the methodology based on fuzzy sets theory is used both in fault tree and event tree analyses. This paper just presents our work in this issue, which resulted…