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
Minimal NFA and biRFSA languages
In this paper, we define the notion of biRFSA which is a residual finate state automaton (RFSA) whose the reverse is also an RFSA. The languages recognized by such automata are called biRFSA languages. We prove that the canonical RFSA of a biRFSA language is a minimal NFA for this language and that each minimal NFA for this language is a sub-automaton of the canonical RFSA. This leads to a characterization of the family of biRFSA languages. In the second part of this paper, we define the family...
Minimal NFA and biRFSA Languages
In this paper, we define the notion of biRFSA which is a residual finate state automaton (RFSA) whose the reverse is also an RFSA. The languages recognized by such automata are called biRFSA languages. We prove that the canonical RFSA of a biRFSA language is a minimal NFA for this language and that each minimal NFA for this language is a sub-automaton of the canonical RFSA. This leads to a characterization of the family of biRFSA languages. In the second part of this paper, we define the family...