On a subclass of context-free groups
On a test for codes.
On a unification problem related to Kreisel's conjecture
On a World Wide Web-Based Planning Support System
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.
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.
On algebraic specifications of computable algebras with the discriminator technique
On ambiguity in DOS systems
On an algorithm for a double-resolvability test.
On an algorithm to decide whether a free group is a free factor of another
We revisit the problem of deciding whether a finitely generated subgroup is a free factor of a given free group . Known algorithms solve this problem in time polynomial in the sum of the lengths of the generators of and exponential in the rank of . We show that the latter dependency can be made exponential in the rank difference rank - rank, which often makes a significant change.
On an algorithm to decide whether a free group is a free factor of another
We revisit the problem of deciding whether a finitely generated subgroup H is a free factor of a given free group F. Known algorithms solve this problem in time polynomial in the sum of the lengths of the generators of H and exponential in the rank of F. We show that the latter dependency can be made exponential in the rank difference rank(F) - rank(H), which often makes a significant change.
On an application of the work of D.E. Knuth to semigroups.
On an equivalence of system-theoretical and categorical concepts
On (anti) conditional independence in Dempster-Shafer theory.
This paper verifies a result of [9] concerning graphoidal structure of Shenoy's notion of independence for Dempster-Shafer theory belief functions. Shenoy proved that his notion of independence has graphoidal properties for positive normal valuations. The requirement of strict positive normal valuations as prerequisite for application of graphoidal properties excludes a wide class of DS belief functions. It excludes especially so-called probabilistic belief functions. It is demonstrated that the...
On approximating NP-hard optimization problems.
On approximation of locally compact groups by finite algebraic systems.
On automatic infinite permutations∗
An infinite permutation α is a linear ordering of N. We study properties of infinite permutations analogous to those of infinite words, and show some resemblances and some differences between permutations and words. In this paper, we try to extend to permutations the notion of automaticity. As we shall show, the standard definitions which are equivalent in the case of words are not equivalent in the context of permutations. We investigate the relationships...
On automatic infinite permutations
An infinite permutation α is a linear ordering of N. We study properties of infinite permutations analogous to those of infinite words, and show some resemblances and some differences between permutations and words. In this paper, we try to extend to permutations the notion of automaticity. As we shall show, the standard definitions which are equivalent in the case of words are not equivalent in the context of permutations. We investigate the relationships between these definitions and prove that...