Lyndon factorization of generalized words of Thue.
Łukasiewicz language and diagonals of formal series. (Langage de Łukasiewicz et diagonales de séries formelles.)
Maintaining the Minimal Distance of a Point Set in Poly-logarithmic Time.
Markov Chains Connected to the Process of Generation of the Words by a Generative System
Matematický popis přirozených jazyků
Mathematical theory of free rhythm
Mathematical theory of static systems
Matrix versions of aperiodic -rational identities
Maximal circular codes versus maximal codes
We answer to a question of De Luca and Restivo whether there exists a circular code which is maximal as circular code and not as code.
Maximal circular codes versus maximal codes
We answer to a question of De Luca and Restivo whether there exists a circular code which is maximal as circular code and not as code.
Maximal prefix products.
Maximality of codes in free monoids
Maximum Semi-Matching Problem in Bipartite Graphs
An (f, g)-semi-matching in a bipartite graph G = (U ∪ V,E) is a set of edges M ⊆ E such that each vertex u ∈ U is incident with at most f(u) edges of M, and each vertex v ∈ V is incident with at most g(v) edges of M. In this paper we give an algorithm that for a graph with n vertices and m edges, n ≤ m, constructs a maximum (f, g)-semi-matching in running time O(m ⋅ min [...] ) Using the reduction of [5] our result on maximum (f, g)-semi-matching problem directly implies an algorithm for the optimal...
Measuring static complexity.
Measuring the problem-relevant information in input
We propose a new way of characterizing the complexity of online problems. Instead of measuring the degradation of the output quality caused by the ignorance of the future we choose to quantify the amount of additional global information needed for an online algorithm to solve the problem optimally. In our model, the algorithm cooperates with an oracle that can see the whole input. We define the advice complexity of the problem to be the minimal number of bits (normalized per input request, and...
Mechanized experiment planning in automaton-environment systems
Medze efektivnosti paralelných výpočtových systémov
Memory complexity of countable functions
Mince zajímají nejen numismatiky
V článku představíme dva druhy úloh týkajících se platby mincemi, které souvisejí s optimalitou počtu použitých mincí. V případě problému platby (říká se také rozměňování — anglicky change making problem), tj. skládání částky z mincí bez možnosti vracení, jsou úlohy spojené s optimalitou dobře prozkoumané. Analogické úlohy zformulujeme pro směnu, tj. skládání částky z mincí s možností vracení. Zde zůstává naopak řada problémů otevřená.
Minimal generators of submonoids of