Special issue dedicated to the thirteenth “Journées Montoises d'Informatique Théorique”
Special issue dedicated to the thirteenth "Journées Montoises d'Informatique Théorique"
Spécialisation de la suite de Sturm et sous-résultants (I)
Speeding up the computations on an elliptic curve using addition-subtraction chains
Spezielle Gleichungen in freien Halbgruppen und eine Anwendung auf Normalformen regulärer Ereignisse
Square-free and overlap-free words
Squares and overlaps in the Thue-Morse sequence and some variants
We consider the position and number of occurrences of squares in the Thue-Morse sequence, and show that the corresponding sequences are 2-regular. We also prove that changing any finite but nonzero number of bits in the Thue-Morse sequence creates an overlap, and any linear subsequence of the Thue-Morse sequence (except those corresponding to decimation by a power of 2) contains an overlap.
Srovnání poloautomatických a automatických kalkulačních strojů z hlediska potřeb numerických metod algebry a analysy
Stable meet semilattice fibrations and free restriction categories.
Stackautomaten in Labyrinthen.
State complexity of cyclic shift
The cyclic shift of a language , defined as =, is an operation known to preserve both regularity and context-freeness. Its descriptional complexity has been addressed in Maslov’s pioneering paper on the state complexity of regular language operations [Soviet Math. Dokl. 11 (1970) 1373–1375], where a high lower bound for partial DFAs using a growing alphabet was given. We improve this result by using a fixed 4-letter alphabet, obtaining a lower bound (n-1)! 2, which shows that the state complexity...
State complexity of cyclic shift
The cyclic shift of a language L, defined as SHIFT(L) = {vu | uv ∈ L}, is an operation known to preserve both regularity and context-freeness. Its descriptional complexity has been addressed in Maslov's pioneering paper on the state complexity of regular language operations [Soviet Math. Dokl.11 (1970) 1373–1375], where a high lower bound for partial DFAs using a growing alphabet was given. We improve this result by using a fixed 4-letter alphabet, obtaining a lower bound (n-1)! . 2(n-1)(n-2), which...
State hypergroups of automata
State spaces and dipaths up to dihomotopy.
Statistical theory of logical derivability
Statistics and computability
Stochastic bottleneck transportation problem with flexible supply and demand quantity
We consider the following bottleneck transportation problem with both random and fuzzy factors. There exist supply points with flexible supply quantity and demand points with flexible demand quantity. For each supply-demand point pair, the transportation time is an independent positive random variable according to a normal distribution. Satisfaction degrees about the supply and demand quantity are attached to each supply and each demand point, respectively. They are denoted by membership functions...
Storing the Subdivision of a Polyhedral Surface.
Straight-line drawings of binary trees with linear area and arbitrary aspect ratio.
Strategies to scan pictures with automata based on Wang tiles
Wang automata are devices for picture language recognition recently introduced by us, which characterize the class REC of recognizable picture languages. Thus, Wang automata are equivalent to tiling systems or online tessellation acceptors, and are based like Wang systems on labeled Wang tiles. The present work focus on scanning strategies, to prove that the ones Wang automata are based on are those following four kinds of movements: boustrophedonic, “L-like”, “U-like”, and spirals.