Search

In the Stanley lattice defined on Dyck paths of size $n$, cover relations are obtained by replacing a valley $DU$ by a peak $UD$. We investigate a greedy version of this lattice, first introduced by Chenevi\`ere, where cover relations replace a factor $DU^k D$ by $U^kD^2$. By relating this poset to another poset recently defined by Nadeau and Tewari, we prove that this still yields a lattice, which we call the ascent lattice $L_n$. We then count intervals in $L_n$. Their generating function is found to be algebraic of degree $3$. The proof is based on a recursive decomposition of intervals involving two catalytic parameters. The solution of the corresponding functional equation is inspired by recent work on the enumeration of walks confined to a quadrant. We also consider the order induced in $L_{mn}$ on $m$-Dyck paths, that is, paths in which all ascent lengths are multiples of $m$, and on mirrored $m$-Dyck paths, in which all descent lengths are multiples of $m$. The first poset $L_{m,n}$ is still a lattice for any $m$, while the second poset $L'_{m,n}$ is only a join semilattice when $m>1$. In both cases, the enumeration of intervals is still described by an equation in two catalytic variables. Interesting connections arise with the sylvester congruence of Hivert, Novelli and Thibon, and again with walks confined to a quadrant. We combine the latter connection with probabilistic results to give asymptotic estimates of the number of intervals in both $L_{m,n}$ and $L'_{m,n}$. Their form implies that the generating functions of intervals are no longer algebraic, nor even D-finite, when $m>1$., Comment: 35 pages

We develop Kummer theory for algebraic function fields in finitely many transcendental variables. We consider any finitely generated Kummer extension (possibly, over a cyclotomic extension) of an algebraic function field, and describe the structure of its Galois group. Our results show in a precise sense how the questions of computing the degrees of these extensions and of computing the group structures of their Galois groups reduce to the corresponding questions for the Kummer extensions of their constant fields., Comment: 14 pages

In this work, we define flattened Catalan words as Catalan words whose runs of weak ascents have leading terms that appear in weakly increasing order. We provide generating functions, formulas, and asymptotic expressions for the number of flattened Catalan words based on the number of runs of ascents (descents), runs of weak ascents (descents), $\ell$-valleys, valleys, symmetric valleys, $\ell$-peaks, peaks, and symmetric peaks., Comment: arXiv admin note: substantial text overlap with arXiv:2404.05672

Recent advances in autonomous driving for uncrewed ground vehicles (UGVs) have spurred significant development, particularly in challenging terrains. This paper introduces a classification system assessing various UGV deployments reported in the literature. Our approach considers motion distortion features that include internal UGV features, such as mass and speed, and external features, such as terrain complexity, which all influence the efficiency of models and navigation systems. We present results that map UGV deployments relative to vehicle kinetic energy and terrain complexity, providing insights into the level of complexity and risk associated with different operational environments. Additionally, we propose a motion distortion metric to assess UGV navigation performance that does not require an explicit quantification of motion distortion features. Using this metric, we conduct a case study to illustrate the impact of motion distortion features on modeling accuracy. This research advocates for creating a comprehensive database containing many different motion distortion features, which would contribute to advancing the understanding of autonomous driving capabilities in rough conditions and provide a validation framework for future developments in UGV navigation systems., Comment: Accepted to the IEEE ICRA Workshop on Field Robotics 2024

In this paper we are interested in the fine-grained complexity of deciding whether there is a homomorphism from an input graph $G$ to a fixed graph $H$ (the $H$-Coloring problem). The starting point is that these problems can be viewed as constraint satisfaction problems (CSPs), and that (partial) polymorphisms of binary relations are of paramount importance in the study of complexity classes of such CSPs. Thus, we first investigate the expressivity of binary symmetric relations $E_H$ and their corresponding (partial) polymorphisms pPol($E_H$). For irreflexive graphs we observe that there is no pair of graphs $H$ and $H'$ such that pPol($E_H$) $\subseteq$ pPol($E_{H'}$), unless $E_{H'}= \emptyset$ or $H =H'$. More generally we show the existence of an $n$-ary relation $R$ whose partial polymorphisms strictly subsume those of $H$ and such that CSP($R$) is NP-complete if and only if $H$ contains an odd cycle of length at most $n$. Motivated by this we also describe the sets of total polymorphisms of nontrivial cliques, odd cycles, as well as certain cores, and we give an algebraic characterization of projective cores. As a by-product, we settle the Okrasa and Rz\k{a}\.zewski conjecture for all graphs of at most 7 vertices.

We provide generating functions, formulas, and asymptotic expressions for the number of Catalan words based on the number of runs of ascents (descents), runs of weak ascents (descents), $\ell$-valleys, valleys, symmetric valleys, $\ell$-peaks, peaks, and symmetric peaks. We also establish some bijections with restricted Dyck paths and ordered trees that transports some statistics.

We study the enumeration of different classes of grand knight's paths in the plane. In particular, we focus on the subsets of zigzag knight's paths subject to constraints. These constraints include ending at ordinate 0, bounded by a horizontal line, confined within a tube, among other considerations. We present our results using generating functions or direct closed-form expressions. We derive asymptotic results, finding approximations for quantities such as the probability that a zigzag knight's path stays in some area of the plane, or for the average of the final height of such a path. Additionally, we exhibit some bijections between grand zigzag knight's paths and some pairs of compositions., Comment: 21 pages, 9 figures

A word $w=w_1\cdots w_n$ over the set of positive integers is a Motzkin word whenever $w_1=\texttt{1}$, $1\leq w_k\leq w_{k-1}+1$, and $w_{k-1}\neq w_{k}$ for $k=2, \dots, n$. It can be associated to a $n$-column Motzkin polyomino whose $i$-th column contains $w_i$ cells, and all columns are bottom-justified. We reveal bijective connections between Motzkin paths, restricted Catalan words, primitive \L{}ukasiewicz paths, and Motzkin polyominoes. Using the aforementioned bijections together with classical one-to-one correspondence with Dyck paths avoiding $UDU$s, we provide generating functions with respect to the length, area, semiperimeter, value of the last symbol, and number of interior points of Motzkin polyominoes. We give asymptotics and closed-form expressions for the total area, total semiperimeter, sum of the last symbol values, and total number of interior points over all Motzkin polyominoes of a given length. We also present and prove an engaging trinomial relation concerning the number of cells lying at different levels and first terms of the expanded $(1+x+x^2)^n$., Comment: 21 pages, 11 figures

We propose a novel angular velocity estimation method to increase the robustness of Simultaneous Localization And Mapping (SLAM) algorithms against gyroscope saturations induced by aggressive motions. Field robotics expose robots to various hazards, including steep terrains, landslides, and staircases, where substantial accelerations and angular velocities can occur if the robot loses stability and tumbles. These extreme motions can saturate sensor measurements, especially gyroscopes, which are the first sensors to become inoperative. While the structural integrity of the robot is at risk, the resilience of the SLAM framework is oftentimes given little consideration. Consequently, even if the robot is physically capable of continuing the mission, its operation will be compromised due to a corrupted representation of the world. Regarding this problem, we propose a way to estimate the angular velocity using accelerometers during extreme rotations caused by tumbling. We show that our method reduces the median localization error by 71.5 % in translation and 65.5 % in rotation and reduces the number of SLAM failures by 73.3 % on the collected data. We also propose the Tumbling-Induced Gyroscope Saturation (TIGS) dataset, which consists of outdoor experiments recording the motion of a lidar subject to angular velocities four times higher than other available datasets. The dataset is available online at https://github.com/norlab-ulaval/Norlab_wiki/wiki/TIGS-Dataset., Comment: 7 pages, 7 figures, submitted to the 2024 IEEE International Conference on Robotics and Automation (ICRA2024), Yokohama, Japan

It follows from the Grothendieck-Ogg-Shafarevich formula that the rank of an abelian variety (with trivial trace) defined over the function field of a curve is bounded by a quantity which depends on the genus of the base curve and on bad reduction data. Using a function field version of classical $\ell$-descent techniques, we derive an arithmetic refinement of this bound, extending previous work of the second and third authors from elliptic curves to abelian varieties, and improving on their result in the case of elliptic curves. When the abelian variety is the Jacobian of a hyperelliptic curve, we produce a more explicit $2$-descent map. Then we apply this machinery to studying points on the Jacobians of certain genus $2$ curves over $k(t)$, where $k$ is some perfect base field of characteristic not $2$., Comment: 19 pages. Minor changes in the exposition

An accurate motion model is a fundamental component of most autonomous navigation systems. While much work has been done on improving model formulation, no standard protocol exists for gathering empirical data required to train models. In this work, we address this issue by proposing Data-driven Robot Input Vector Exploration (DRIVE), a protocol that enables characterizing uncrewed ground vehicles (UGVs) input limits and gathering empirical model training data. We also propose a novel learned slip approach outperforming similar acceleration learning approaches. Our contributions are validated through an extensive experimental evaluation, cumulating over 7 km and 1.8 h of driving data over three distinct UGVs and four terrain types. We show that our protocol offers increased predictive performance over common human-driven data-gathering protocols. Furthermore, our protocol converges with 46 s of training data, almost four times less than the shortest human dataset gathering protocol. We show that the operational limit for our model is reached in extreme slip conditions encountered on surfaced ice. DRIVE is an efficient way of characterizing UGV motion in its operational conditions. Our code and dataset are both available online at this link: https://github.com/norlab-ulaval/DRIVE., Comment: 8 pages, 7 figures, 1 table, accepted for publication at the 2024 IEEE International Conference on Robotics and Automation (ICRA2024), Yokohama, Japan

We introduce a new poset structure on Dyck paths where the covering relation is a particular case of the relation inducing the Tamari lattice. We prove that the transitive closure of this relation endows Dyck paths with a lattice structure. We provide a trivariate generating function counting the number of Dyck paths with respect to the semilength, the numbers of outgoing and incoming edges in the Hasse diagram. We deduce the numbers of coverings, meet and join irreducible elements. As a byproduct, we present a new involution on Dyck paths that transports the bistatistic of the numbers of outgoing and incoming edges into its reverse. Finally, we give a generating function for the number of intervals, and we compare this number with the number of intervals in the Tamari lattice.

Let $\sum a_nx^n\in\bar{\mathbb{Q}}[[x]]$ be the power series representation of a rational function and let $f:\ \{0,1,\ldots\}\rightarrow \bar{\mathbb{Q}}$ be a so-called almost quasi-polynomial. Under a necessary stability condition, we prove that $\sum f(n)a_nx^n$ satisfies the P\'olya-Carlson dichotomy: it is either a rational function or it cannot be extended analytically to a strictly larger domain than its disk of convergence. This latter property is much stronger than being transcendental. The first application and motivation of our result is the solution of a conjecture by Byszewski-Cornelissen. This gives a complete understanding of the analytic continuation behavior of the Artin-Mazur zeta function associated to a dynamical system on an abelian variety. Further applications include the solution of a conjecture by Bell-Miles-Ward and a significant case of an open problem by Royals-Ward., Comment: 20 pages

Motivated by the definition of tropical schemes and the schematic tropicalization of algebraic varieties defined over a non-Archimedean field, we introduce an algebraic process for the tropicalization of schemes and Zariski sheaves of rings and of modules over them. For us, tropicalization is understood in the broader sense of a process that associates idempotent algebraic objects to the usual ones from algebraic geometry. This goal is achieved by first building the affine case and then globalizing the construction in a functorial way for a fixed affine open covering of a given scheme. Our constructions are possible thanks to the algebraic interpretation of order-theoretic structures through the theory of commutative algebra for idempotent semirings. We define the notions of realizable semirings and realizable semimodules, and we show that they are suitable for our formalism due to the fact that their lattices of subobjects are, in a precise way, a combinatorial reflection of lattices coming from commutative algebra., Comment: 31 pages. In subsection 4.1, we restricted to integral realizable semirings due to technicalities. New results were added to subsection 4.2. The clarity of the exposition was improved in different parts of the text

We investigate the parameterized complexity of several problems formalizing cluster identification in graphs. In other words we ask whether a graph contains a large enough and sufficiently connected subgraph. We study here three relaxations of CLIQUE: $s$-CLUB and $s$-CLIQUE, in which the relaxation is focused on the distances in respectively the cluster and the original graph, and $\gamma$-COMPLETE SUBGRAPH in which the relaxation is made on the minimal degree in the cluster. As these three problems are known to be NP-hard, we study here their parameterized complexities. We prove that $s$-CLUB and $s$-CLIQUE are NP-hard even restricted to graphs of degeneracy $\le 3$ whenever $s \ge 3$, and to graphs of degeneracy $\le 2$ whenever $s \ge 5$, which is a strictly stronger result than its W[1]-hardness parameterized by the degeneracy. We also obtain that these problems are solvable in polynomial time on graphs of degeneracy $1$. Concerning $\gamma$-COMPLETE SUBGRAPH, we prove that it is W[1]-hard parameterized by both the degeneracy, which implies the W[1]-hardness parameterized by the number of vertices in the $\gamma$-complete-subgraph, and the number of elements outside the $\gamma$-complete subgraph.

This work is a continuation of some recent articles presenting enumerative results for Catalan words avoiding one or a pair of consecutive or classical patterns of length $3$. More precisely, we provide systematically the bivariate generating function for the number of Catalan words avoiding a given pair of relations with respect to the length and the number of descents. We also present several constructive bijections preserving the number of descents. As a byproduct, we deduce the generating function for the total number of descents on all Catalan words of a given length and avoiding a pair of ordered relations.

Motzkin paths with air pockets (MAP) of the first kind are defined as a generalization of Dyck paths with air pockets. They are lattice paths in $\mathbb{N}^2$ starting at the origin made of steps $U=(1,1)$, $D_k=(1,-k)$, $k\geq 1$ and $H=(1,0)$, where two down-steps cannot be consecutive. We enumerate MAP and their prefixes avoiding peaks (resp. valleys, resp. double rise) according to the length, the type of the last step, and the height of its end-point. We express our results using Riordan arrays. Finally, we provide constructive bijections between these paths and restricted Dyck and Motzkin paths., Comment: arXiv admin note: substantial text overlap with arXiv:2212.12404

Motzkin paths with air pockets (MAP) are defined as a generalization of Dyck paths with air pockets by adding some horizontal steps with certain conditions. In this paper, we introduce two generalizations. The first one consists of lattice paths in $\Bbb{N}^2$ starting at the origin made of steps $U=(1,1)$, $D_k=(1,-k)$, $k\geq 1$ and $H=(1,0)$, where two down steps cannot be consecutive, while the second one are lattice paths in $\Bbb{N}^2$ starting at the origin, made of steps $U$, $D_k$ and $H$, where each step $D_k$ and $H$ is necessarily followed by an up step, except for the last step of the path. We provide enumerative results for these paths according to the length, the type of the last step, and the height of its end-point. A similar study is made for these paths read from right to left. As a byproduct, we obtain new classes of paths counted by the Motzkin numbers. Finally, we express our results using Riordan arrays.

Grand Dyck paths with air pockets (GDAP) are a generalization of Dyck paths with air pockets by allowing them to go below the $x$-axis. We present enumerative results on GDAP (or their prefixes) subject to various restrictions such as maximal/minimal height, ordinate of the last point and particular first return decomposition. In some special cases we give bijections with other known combinatorial classes., Comment: 20 pages, 4 figures

In the context of autonomous driving, vehicles are inherently bound to encounter more extreme weather during which public safety must be ensured. As climate is quickly changing, the frequency of heavy snowstorms is expected to increase and become a major threat to safe navigation. While there is much literature aiming to improve navigation resiliency to winter conditions, there is a lack of standard metrics to quantify the loss of visibility of lidar sensors related to precipitation. This chapter proposes a novel metric to quantify the lidar visibility loss in real time, relying on the notion of visibility from the meteorology research field. We evaluate this metric on the Canadian Adverse Driving Conditions (CADC) dataset, correlate it with the performance of a state-of-the-art lidar-based localization algorithm, and evaluate the benefit of filtering point clouds before the localization process. We show that the Iterative Closest Point (ICP) algorithm is surprisingly robust against snowfalls, but abrupt events, such as snow gusts, can greatly hinder its accuracy. We discuss such events and demonstrate the need for better datasets focusing on these extreme events to quantify their effect., Comment: Submitted to Intelligent Vehicles and Transportation Volume 3 - De Gruyter

We investigate the fine-grained and the parameterized complexity of several generalizations of binary constraint satisfaction problems (BINARY-CSPs), that subsume variants of graph colouring problems. Our starting point is the observation that several algorithmic approaches that resulted in complexity upper bounds for these problems, share a common structure. We thus explore an algebraic approach relying on semirings that unifies different generalizations of BINARY-CSPs (such as the counting, the list, and the weighted versions), and that facilitates a general algorithmic approach to efficiently solving them. The latter is inspired by the (component) twin-width parameter introduced by Bonnet et al., which we generalize via edge-labelled graphs in order to formulate it to arbitrary binary constraints. We consider input instances with bounded component twin-width, as well as constraint templates of bounded component twin-width, and obtain an FPT algorithm as well as an improved, exponential-time algorithm, for broad classes of binary constraints. We illustrate the advantages of this framework by instantiating our general algorithmic approach on several classes of problems (e.g., the $H$-coloring problem and its variants), and showing that it improves the best complexity upper bounds in the literature for several well-known problems., Comment: 25 pages

We provide enumerating results for partial knight's paths of a given size. We prove algebraically that zigzag knight's paths of a given size ending on the $x$-axis are enumerated by the generalized Catalan numbers, and we give a constructive bijection with peakless Motzkin paths of a given length. After enumerating partial knight's paths of a given length, we prove that zigzag knight's paths of a given length ending on the $x$-axis are counted by the Catalan numbers. Finally, we give a constructive bijection with Dyck paths of a given length.

\L{}ukasiewicz paths are lattice paths in $\Bbb{N}^2$ starting at the origin, ending on the $x$-axis, and consisting of steps in the set $\{(1,k), k\geq -1\}$. We give generating function and exact value for the number of $n$-length prefixes (resp. suffixes) of these paths ending at height $k\geq 0$ with a given type of step. We make a similar study for prefixes of height at most $t\geq 0$. Using the explicit forms for the paths of bounded height, we evaluate the average height asymptotically. For fixed $k$ and $n\to\infty$, this quantity behaves as $\sqrt{\pi n}$. Finally we study (in the same way) prefixes of alternate \L{}ukasiewicz paths, i.e., \L{}ukasiewicz paths that do contain two consecutive steps with the same direction.

Data anonymization is often a task carried out by humans. Automating it would reduce the cost and time required to complete this task. This paper presents a pipeline to automate the anonymization of audio data in French. We propose a pipeline, which takes audio files with their transcriptions and removes the named entities (NEs) present in the audio. Our pipeline is made up of a forced aligner, which aligns words in an audio transcript with speech and a model that performs named entity recognition (NER). Then, the audio segments that correspond to NEs are substituted with silence to anonymize audio. We compared forced aligners and NER models to find the best ones for our scenario. We evaluated our pipeline on a small hand-annotated dataset, achieving an F1 score of 0.769. This result shows that automating this task is feasible., Comment: 8 pages

For any pattern $p$ of length at most two, we provide generating functions and asymptotic approximations for the number of $p$-equivalence classes of Dyck paths with catastrophes, where two paths of the same length are $p$-equivalent whenever the positions of the occurrences of the pattern $p$ are the same., Comment: 25 pages, 14 figures, 1 table

We introduce and study the new combinatorial class of Dyck paths with air pockets. We exhibit a bijection with the peakless Motzkin paths which transports several pattern statistics and give bivariate generating functions for the distribution of patterns as peaks, returns and pyramids. Then, we deduce the popularities and asymptotic expectations of these patterns and point out a link between the popularity of pyramids and a special kind of closed smooth self-overlapping curves, a subset of Fibonacci meanders. A similar study is conducted for non-decreasing Dyck paths with air pockets., Comment: 20 pages, 3 figures, 2 tables

Challenges inherent to autonomous wintertime navigation in forests include lack of reliable a Global Navigation Satellite System (GNSS) signal, low feature contrast, high illumination variations and changing environment. This type of off-road environment is an extreme case of situations autonomous cars could encounter in northern regions. Thus, it is important to understand the impact of this harsh environment on autonomous navigation systems. To this end, we present a field report analyzing teach-and-repeat navigation in a subarctic forest while subject to fluctuating weather, including light and heavy snow, rain and drizzle. First, we describe the system, which relies on point cloud registration to localize a mobile robot through a boreal forest, while simultaneously building a map. We experimentally evaluate this system in over 18.8 km of autonomous navigation in the teach-and-repeat mode. Over 14 repeat runs, only four manual interventions were required, three of which were due to localization failure and another one caused by battery power outage. We show that dense vegetation perturbs the GNSS signal, rendering it unsuitable for navigation in forest trails. Furthermore, we highlight the increased uncertainty related to localizing using point cloud registration in forest trails. We demonstrate that it is not snow precipitation, but snow accumulation, that affects our system's ability to localize within the environment. Finally, we expose some challenges and lessons learned from our field campaign to support better experimental work in winter conditions. Our dataset is available online., Comment: Published in Field Robotics Volume 2. Paper number 50

In 1985, Schoof devised an algorithm to compute zeta functions of elliptic curves over finite fields by directly computing the numerators of these rational functions modulo sufficiently many primes (see \cite{schoof_1985}). If $E/K$ is an elliptic curve with nonconstant $j$-invariant defined over a function field $K$ of characteristic $p \geq 5$, we know that its $L$-function $L(T,E/K)$ is a polynomial in $\mathbb{Z}[T]$ (see \cite[p.11]{katz_2002}). Inspired by Schoof, we study the reduction of $L(T,E/K)$ modulo integers. We obtain three main results. Firstly, if $E/K$ has non-trivial $K$-rational $N$-torsion for some integer $N$ coprime with $p$, we extend a formula for $L(T,E/K) \bmod N$ due to Hall (see \cite[p.133, Theorem 4]{hall_2006}) to all quadratic twists $E_f/K$ with $f \in K^\times \smallsetminus K^{\times 2}$. Secondly, without any condition on the $2$-torsion subgroup of $E(K)$, we give a formula for the quotient modulo $2$ of $L$-functions of any two quadratic twists of $E/K$. Thirdly, we use these results to compute the global root numbers of an infinite family of quadratic twists of an elliptic curve and in most cases find the exact analytic rank of each of these twists. We also illustrate that in favourable situations our second main result allows one to compute much more efficiently $L(T,E_f/K) \bmod 2$ than an algorithm of Baig and Hall (see \cite{baig_hall_2012}). Finally, we use our formulas to compute directly some degree $2$ $L$-functions., Comment: 29 pages [previously 10 pages]. Expanded version of Chapter 3 of the PhD thesis of the author. Comments welcome

We present a field report of CTU-CRAS-NORLAB team from the Subterranean Challenge (SubT) organised by the Defense Advanced Research Projects Agency (DARPA). The contest seeks to advance technologies that would improve the safety and efficiency of search-and-rescue operations in GPS-denied environments. During the contest rounds, teams of mobile robots have to find specific objects while operating in environments with limited radio communication, e.g. mining tunnels, underground stations or natural caverns. We present a heterogeneous exploration robotic system of the CTU-CRAS-NORLAB team, which achieved the third rank at the SubT Tunnel and Urban Circuit rounds and surpassed the performance of all other non-DARPA-funded teams. The field report describes the team's hardware, sensors, algorithms and strategies, and discusses the lessons learned by participating at the DARPA SubT contest., Comment: This paper have already been accepted to be published Filed Robotics special issue about DARPA SubT challange

We consider the system of equations $A_k(x)=p(x)A_{k-1}(x)(q(x)+\sum_{i=0}^k A_i(x))$ for $k\geq r+1$ where $A_i(x)$, $0\leq i \leq r$, are some given functions and show how to obtain a close form for $A(x)=\sum_{k\geq 0}A_k(x)$. We apply this general result to the enumeration of certain subsets of Dyck, Motzkin, skew Dyck, and skew Motzkin paths, defined recursively according to the first return decomposition with a monotonically non-increasing condition relative to the maximal ordinate reached by an occurrence of a given pattern $\pi$., Comment: 6 pages, 4 tables