1,721,028 research outputs found
Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence
No full textIn this paper, we enumerate two families of pattern-avoiding permutations: those avoiding the vincular pattern 2\underbracket{41}3, which we call semi-Baxter permutations, and those avoiding the vincular patterns 2\underbracket{41}3, 3\underbracket{14}2, and 3\underbracket{41}2, which we call strong-Baxter permutations. We call semi-Baxter numbers and strong-Baxter numbers the associated enumeration sequences. We prove that the semi-Baxter numbers enumerate in addition plane permutations (avoiding 2\underbracket{14}3). The problem of counting these permutations was open and has given rise to several conjectures, which we also prove in this paper. For each family (that of semi-Baxter---or, equivalently, plane---and that of strong-Baxter permutations), we describe a generating tree, which translates into a functional equation for the generating function. For semi-Baxter permutations, it is solved using (a variant of) the kernel method: this gives an expression for the generating function while also proving its D-finiteness. From the obtained generating function, we derive closed formulas for the semi-Baxter numbers, a recurrence that they satisfy, as well as their asymptotic behavior. For strong-Baxter permutations, we show that their generating function is (a slight modification of) that of a family of walks in the quarter plane, which is known to be non--D-finite
Permutation classes and polyomino classes with excluded submatrices
No full textThis article introduces an analogue of permutation classes in the context of polyominoes. For both permutation classes and polyomino classes, we present an original way of characterizing them by avoidance constraints (namely, with excluded submatrices) and we discuss how canonical such a description by submatrix-avoidance can be. We provide numerous examples of permutation and polyomino classes which may be defined and studied from the submatrix-avoidance point of view, and conclude with various directions for future research on this topic
Structural and Algorithmic Properties of Permutation Classes
No full textIn this thesis, we study the relationship between the structure of permutation classes and the computational complexity of different decision problems. First, we explore the structure of permutation classes through the lens of various parameters, with a particular interest in tree-width. We define novel structural properties of a general permutation class C, the most notable being the long path property. Using these properties, we infer lower bounds on the maximum tree-width attained by a permutation of length n in C. For example, we prove that any class with the long path property has unbounded tree-width. The main decision problem we consider is known as Permutation Pattern Match- ing (PPM). The input of PPM consists of a pair of permutations τ (the 'text') and π (the 'pattern'), and the goal is to decide whether τ contains π as a subpermutation. Af- ter briefly considering general PPM, we focus on its pattern-restricted variant known as C-Pattern PPM where we additionally require that the pattern π comes from a fixed class C. We derive both classical and parameterized hardness results assuming different structural properties of C. For example, we show that C-Pattern PPM is NP-complete whenever C has the long path property. Furthermore, we focus on an even more restricted variant of PPM where the text is..
Strukturální a algoritmické vlastnosti permutačních tříd
No full textV této práci studujeme vztah mezi strukturou dědičných permutačních tříd a výpo- četní složitostí různých rozhodovacích problémů. Nejdříve zkoumáme strukturu permu- tačních tříd z pohledu několika různých parametrů, zejména stromové šířky. Definujeme nové vlastnosti obecné permutační třídy C, z nichž nejdůležitější je vlastnost dlouhé cesty. Z těchto vlastností pak odvodíme různé dolní odhady na to jakou největší stromovou šířku může mít permutace délky n z třídy C. Například dokážeme, že libovolná třída s vlastností dlouhé cesty má stromovou šířku neomezenou. Hlavní rozhodovací problém, kterým se zabýváme, je znám jako Permutation Pat- tern Matching (PPM). Vstupem pro problém PPM je dvojice permutací τ (text) a π (vzor), a cílem je rozhodnout jestli τ obsahuje π jako podpermutaci. Nejdříve zběžně uvažujeme problém PPM ve své obecné verzi, a poté se zaměříme na jeho variantu C- Pattern PPM, kde navíc požadujeme, aby vzor π pocházel z pevně dané třídy C. Za předpokladu různých strukturálních vlastností třídy C pak odvodíme jak klasické tak pa- rametrizované těžkostní výsledky. Například ukážeme, že problém C-Pattern PPM je NP-úplný kdykoliv třída C má vlastnost dlouhé cesty. Dále se zaměříme na ještě více omezenou variantu problému PPM, ve které požadu- jeme, aby i text pocházel z pevně dané třídy C. Tento...In this thesis, we study the relationship between the structure of permutation classes and the computational complexity of different decision problems. First, we explore the structure of permutation classes through the lens of various parameters, with a particular interest in tree-width. We define novel structural properties of a general permutation class C, the most notable being the long path property. Using these properties, we infer lower bounds on the maximum tree-width attained by a permutation of length n in C. For example, we prove that any class with the long path property has unbounded tree-width. The main decision problem we consider is known as Permutation Pattern Match- ing (PPM). The input of PPM consists of a pair of permutations τ (the 'text') and π (the 'pattern'), and the goal is to decide whether τ contains π as a subpermutation. Af- ter briefly considering general PPM, we focus on its pattern-restricted variant known as C-Pattern PPM where we additionally require that the pattern π comes from a fixed class C. We derive both classical and parameterized hardness results assuming different structural properties of C. For example, we show that C-Pattern PPM is NP-complete whenever C has the long path property. Furthermore, we focus on an even more restricted variant of PPM where the text is...Informatický ústav Univerzity KarlovyComputer Science Institute of Charles UniversityMatematicko-fyzikální fakultaFaculty of Mathematics and Physic
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
On the enumeration of d-minimal permutations
No full textInternational audienceWe suggest an approach for the enumeration of minimal permutations having d descents which uses skew Young tableaux. We succeed in finding a general expression for the number of such permutations in terms of (several) sums of determinants. We then generalize the class of skew Young tableaux under consideration; this allows in particular to discover some presumably new results concerning Eulerian numbers
The Longest Common Pattern Problem for two Permutations
Full text linkInternational audienceIn this paper, we give a polynomial (O(n^8)) algorithm for finding a longest common pattern between two permutations of size n given that one is separable. We also give an algorithm for general permutations whose complexity depends on the length of the longest simple permutation involved in one of our permutations
- …
