Search results for " Computer Science"
showing 10 items of 3983 documents
Distance graphs and the T-coloring problem
1999
Abstract The T-coloring problem is, given a graph G = (V, E), a set T of nonnegative integers containing 0, and a ‘span’ bound s ⩾ 0, to compute an integer coloring f of the vertices of G such that |f(ν) − f(w)| ∉ T ∀νw ∈ E and max f − min f ⩽ s. This problem arises in the planning of channel assignments for broadcast networks. When restricted to complete graphs, the T-coloring problem boils down to a number problem which can be solved efficiently for many types of sets T. The paper presents results indicating that this is not the case if the set T is arbitrary. To these ends, the class of distance graphs is introduced, which consists of all graphs G : G ≅ G(A) for some (finite) set of posi…
Rough Set Algebras as Description Domains
2009
Study of the so called knowledge ordering of rough sets was initiated by V.W. Marek and M. Truszczynski at the end of 90-ies. Under this ordering, the rough sets of a fixed approximation space form a domain in which every set ↓ is a Boolean algebra. In the paper, an additional operation inversion on rough set domains is introduced and an abstract axiomatic description of obtained algebras of rough set is given. It is shown that the resulting class of algebras is essentially different from those traditional in rough set theory: it is not definable, for instance, in the class of regular double Stone algebras, and conversely.
On the subset sum problem for finite fields
2021
Abstract Let G be the additive group of a finite field. J. Li and D. Wan determined the exact number of solutions of the subset sum problem over G, by giving an explicit formula for the number of subsets of G of prescribed size whose elements sum up to a given element of G. They also determined a closed-form expression for the case where the subsets are required to contain only nonzero elements. In this paper we give an alternative proof of the two formulas. Our argument is purely combinatorial, as in the original proof by Li and Wan, but follows a different and somehow more “natural” approach. We also indicate some new connections with coding theory and combinatorial designs.
On fixed points of the Burrows-Wheeler transform
2017
The Burrows-Wheeler Transform is a well known transformation widely used in Data Compression: important competitive compression software, such as Bzip (cf. [1]) and Szip (cf. [2]) and some indexing software, like the FM-index (cf. [3]), are deeply based on the Burrows Wheeler Transform. The main advantage of using BWT for data compression consists in its feature of "clustering" together equal characters. In this paper we show the existence of fixed points of BWT, i.e., words on which BWT has no effect. We show a characterization of the permutations associated to BWT of fixed points and we give the explicit form of fixed points on a binary ordered alphabet a, b having at most four b's and th…
Epichristoffel Words and Minimization of Moore Automata
2014
This paper is focused on the connection between the combinatorics of words and minimization of automata. The three main ingredients are the epichristoffel words, Moore automata and a variant of Hopcroft's algorithm for their minimization. Epichristoffel words defined in [14] generalize some properties of circular sturmian words. Here we prove a factorization property and the existence of the reduction tree, that uniquely identifies the structure of the word. Furthermore, in the paper we investigate the problem of the minimization of Moore automata by defining a variant of Hopcroft's minimization algorithm. The use of this variant makes simpler the computation of the running time and consequ…
On the Shuffle of Star-Free Languages
2012
Motivated by the general problem to characterize families of languages closed under shuffle, we investigate some conditions under which the shuffle of two star-free languages is star-free. Some of the special cases here approached give rise to new problems in combinatorics on words.
Inductive Inference with Procrastination: Back to Definitions
1999
In this paper, we reconsider the definition of procrastinating learning machines. In the original definition of Freivalds and Smith [FS93], constructive ordinals are used to bound mindchanges. We investigate possibility of using arbitrary linearly ordered sets to bound mindchanges in similar way. It turns out that using certain ordered sets it is possible to define inductive inference types different from the previously known ones. We investigate properties of the new inductive inference types and compare them to other types.
A note on renewal systems
1992
Abstract A renewal system is a symbolic dynamical system generated by free concatenations of a finite set of words. In this paper we prove that, given two systems which are both renewal and Markov systems, it is decidable whether they are topologically conjugate. The proof makes use of the methods and the techniques of formal language theory.
On the classification of algebraic function fields of class number three
2012
AbstractLet F be an algebraic function field of one variable having a finite field Fq with q>2 elements as its field of constants. We determine all such fields for which the class number is three. More precisely, we show that, up to Fq-isomorphism, there are only 8 of such function fields. For q=2 the problem has been solved under the additional hypothesis that the function field is quadratic.
A smallest irregular oriented graph containing a given diregular one
2004
AbstractA digraph is called irregular if its vertices have mutually distinct ordered pairs of semi-degrees. Let D be any diregular oriented graph (without loops or 2-dicycles). A smallest irregular oriented graph F, F=F(D), is constructed such that F includes D as an induced subdigraph, the smallest digraph being one with smallest possible order and with smallest possible size. If the digraph D is arcless then V(D) is an independent set of F(D) comprising almost all vertices of F(D) as |V(D)|→∞. The number of irregular oriented graphs is proved to be superexponential in their order. We could not show that almost all oriented graphs are/are not irregular.