On locating a single path-like facility in a general graph
On location problems on fuzzy graphs.
Location problems concern a wide set of fields where it is usually assumed that exact data are known. However, in real applications, the location of the facility considered can be full of linguistic vagueness, that can be appropriately modeled using networks with fuzzy values. In that way arise Fuzzy Location Problems; this paper deals with their general formulation and the description solution methods. Namely we show the variety of problems that can be considered in this context and, for some of...
On low-complexity bi-infinite words and their factors
In this paper we study bi-infinite words on two letters. We say that such a word has stiffness if the number of different subwords of length equals for all sufficiently large. The word is called -balanced if the numbers of occurrences of the symbol a in any two subwords of the same length differ by at most . In the present paper we give a complete description of the class of bi-infinite words of stiffness and show that the number of subwords of length from this class has growth order...
On maximal finite antichains in the homomorphism order of directed graphs
We show that the pairs where T is a tree and its dual are the only maximal antichains of size 2 in the category of directed graphs endowed with its natural homomorphism ordering.
On minimal words with given subword complexity.
On Minimum and Maximum Spanning Trees of Linearly Moving Points.
On multiperiodic words
In this note we consider the longest word, which has periods p1,...,pn, and does not have the period gcd(p1,...,pn). The length of such a word can be established by a simple algorithm. We give a short and natural way to prove that the algorithm is correct. We also give a new proof that the maximal word is a palindrome.
On multiplicatively dependent linear numeration systems, and periodic points
Two linear numeration systems, with characteristic polynomial equal to the minimal polynomial of two Pisot numbers and respectively, such that and are multiplicatively dependent, are considered. It is shown that the conversion between one system and the other one is computable by a finite automaton. We also define a sequence of integers which is equal to the number of periodic points of a sofic dynamical system associated with some Parry number.
On multiplicatively dependent linear numeration systems, and periodic points
Two linear numeration systems, with characteristic polynomial equal to the minimal polynomial of two Pisot numbers β and γ respectively, such that β and γ are multiplicatively dependent, are considered. It is shown that the conversion between one system and the other one is computable by a finite automaton. We also define a sequence of integers which is equal to the number of periodic points of a sofic dynamical system associated with some Parry number.
On parallel deletions applied to a word
On permutations generated by infinite binary words.
On planar mixed hypergraphs.
On polynomial time decidability of induced-minor-closed classes
On possible growths of arithmetical complexity
The arithmetical complexity of infinite words, defined by Avgustinovich, Fon-Der-Flaass and the author in 2000, is the number of words of length n which occur in the arithmetical subsequences of the infinite word. This is one of the modifications of the classical function of subword complexity, which is equal to the number of factors of the infinite word of length n. In this paper, we show that the orders of growth of the arithmetical complexity can behave as many sub-polynomial functions. More...
On sampling colorings of bipartite graphs.
On semigroups of matrices over the tropical semiring
On separating sets of words. I.
On separating sets of words. II.
On separating sets of words. III.
On separating sets of words. IV.