Nondeterminism versus determinism of finite automata over directed acyclic graphs.
Note on decipherability of three-word codes.
Nowhere continuous solutions to elliptic systems
NP-completeness of minimal width unordered tree layout.
NP-completeness of the planar separator problems.
NP-completeness results for minimum planar spanners.
NP-hardness results for intersection graphs
Numbering action vertices in workflow graphs
Workflow graphs, consisting of actions, events, and logical switches, are used to model business processes. In order to easily identify the actions within a workflow graph, it is useful to number them in such a way that the numbering reflects the structure of the workflow. However, available tools offer only rudimental numbering schemes. In the paper, a set of natural requirements is defined that a logical numbering should fulfill. It is investigated under what conditions there is an appropriate...
Numerical studies of the asymptotic height distribution in binary search trees.
On a characteristic property of Arnoux–Rauzy sequences
Here we give a characterization of Arnoux–Rauzy sequences by the way of the lexicographic orderings of their alphabet.
On a characteristic property of ARNOUX–RAUZY sequences
Here we give a characterization of Arnoux–Rauzy sequences by the way of the lexicographic orderings of their alphabet.
On a class of Thue-Morse type sequences.
On a code problem concerning planar acyclic graphs
On a devil’s staircase associated to the joint spectral radii of a family of pairs of matrices
The joint spectral radius of a finite set of real matrices is defined to be the maximum possible exponential rate of growth of products of matrices drawn from that set. In previous work with K. G. Hare and J. Theys we showed that for a certain one-parameter family of pairs of matrices, this maximum possible rate of growth is attained along Sturmian sequences with a certain characteristic ratio which depends continuously upon the parameter. In this note we answer some open questions from that paper...
On a generalization of perfect -matching
The paper is concerned with the existence of non-negative or positive solutions to , where is the vertex-edge incidence matrix of an undirected graph. The paper gives necessary and sufficient conditions for the existence of such a solution.
On a paper by Castelli, Mignosi, Restivo
On a paper by Castelli, Mignosi, Restivo
Fine and Wilf's theorem has recently been extended to words having three periods. Following the method of the authors we extend it to an arbitrary number of periods and deduce from that a characterization of generalized Arnoux-Rauzy sequences or episturmian infinite words.
On abelian repetition threshold
We study the avoidance of Abelian powers of words and consider three reasonable generalizations of the notion of Abelian power to fractional powers. Our main goal is to find an Abelian analogue of the repetition threshold, i.e., a numerical value separating k-avoidable and k-unavoidable Abelian powers for each size k of the alphabet. We prove lower bounds for the Abelian repetition threshold for large alphabets and all definitions of Abelian fractional power. We develop a method estimating the exponential...
On Abelian repetition threshold
We study the avoidance of Abelian powers of words and consider three reasonable generalizations of the notion of Abelian power to fractional powers. Our main goal is to find an Abelian analogue of the repetition threshold, i.e., a numerical value separating k-avoidable and k-unavoidable Abelian powers for each size k of the alphabet. We prove lower bounds for the Abelian repetition threshold for large alphabets and all definitions of Abelian fractional ...
On abelian versions of critical factorization theorem
In the paper we study abelian versions of the critical factorization theorem. We investigate both similarities and differences between the abelian powers and the usual powers. The results we obtained show that the constraints for abelian powers implying periodicity should be quite strong, but still natural analogies exist.