One-rule semi-Thue systems with loops of length one, two or three
One-way communication complexity of symmetric boolean functions
We study deterministic one-way communication complexity of functions with Hankel communication matrices. Some structural properties of such matrices are established and applied to the one-way two-party communication complexity of symmetric Boolean functions. It is shown that the number of required communication bits does not depend on the communication direction, provided that neither direction needs maximum complexity. Moreover, in order to obtain an optimal protocol, it is in any case sufficient...
One-way communication complexity of symmetric Boolean functions
We study deterministic one-way communication complexity of functions with Hankel communication matrices. Some structural properties of such matrices are established and applied to the one-way two-party communication complexity of symmetric Boolean functions. It is shown that the number of required communication bits does not depend on the communication direction, provided that neither direction needs maximum complexity. Moreover, in order to obtain an optimal protocol, it is in any case sufficient...
Online coloring known graphs.
On-line 𝓟-coloring of graphs
For a given induced hereditary property 𝓟, a 𝓟-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property 𝓟. We consider the effectiveness of on-line 𝓟-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function of any stingy on-line 𝓟-coloring algorithm. In the class of generalized...
On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems
On-line computations of the ideal lattice of posets
On-line evaluation of powers using Euclid's algorithm
On-line finite automata for addition in some numeration systems
On-line finite automata for addition in some numeration systems
We consider numeration systems where the base is a negative integer, or a complex number which is a root of a negative integer. We give parallel algorithms for addition in these numeration systems, from which we derive on-line algorithms realized by finite automata. A general construction relating addition in base β and addition in base βm is given. Results on addition in base , where b is a relative integer, follow. We also show that addition in base the golden ratio is computable by an on-line...
Online LIB problems : heuristics for bin covering and lower bounds for bin packing
We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items — we call such a version, the LIB version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced here. The...
Online LIB problems: Heuristics for Bin Covering and lower bounds for Bin Packing
We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items — we call such a version, the LIB version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced here. The...
On-line models and algorithms for max independent set
In on-line computation, the instance of the problem dealt is not entirely known from the beginning of the solution process, but it is revealed step-by-step. In this paper we deal with on-line independent set. On-line models studied until now for this problem suppose that the input graph is initially empty and revealed either vertex-by-vertex, or cluster-by-cluster. Here we present a new on-line model quite different to the ones already studied. It assumes that a superset of the final graph is initially...
On-line -adic covering by the method of the -th segment and its application to on-line covering by cubes.
On-Line Steiner Trees in the Euclidean Plane.
Onq-Power Cycles in Cubic Graphs
In the context of a conjecture of Erdős and Gyárfás, we consider, for any q ≥ 2, the existence of q-power cycles (i.e., with length a power of q) in cubic graphs. We exhibit constructions showing that, for every q ≥ 3, there exist arbitrarily large cubic graphs with no q-power cycles. Concerning the remaining case q = 2 (which corresponds to the conjecture of Erdős and Gyárfás), we show that there exist arbitrarily large cubic graphs whose all 2-power cycles have length 4 only, or 8 only.
Ontologies and soft computing in flexible querying
Open shop scheduling with delays
Operating on formal concept abstraction.
The subject of this paper regards a procedure to obtain the abstract form of concepts, directly from their most natural form, thus these can be efficiently learned and the possibility of operating formally on them is reached. The achievement of said type of form results also useful to compute conceptual parameters symbolic and numerical in nature.
Operational Methods in the Environment of a Computer Algebra System
This article presents the principal results of the doctoral thesis “Direct Operational Methods in the Environment of a Computer Algebra System” by Margarita Spiridonova (Institute of mathematics and Informatics, BAS), successfully defended before the Specialised Academic Council for Informatics and Mathematical Modelling on 23 March, 2009.The presented research is related to the operational calculus approach and its representative applications. Operational methods are considered, as well as their...