Some Properties of the Combinational Measure of Complexity of Binary Words
Some properties of the singular words of the Fibonacci word.
Some Provably Hard Crossing Number Problems.
Some remarks on differentiable sequences and recursivity.
Some remarks on multihead automata
Some remarks on the extension of a finite set of stochastic automata
Some remarks on the stability problem for linear space automata and semicontinuity of cut point languages
Some results in discrete mathematics and digital geometry by Professor Dragan Acketa.
Some results on cellular automata
We want to discuss some properties of one-dimensional, radius 1, CUCAs (we denote by CUCA a Computationally Universal Cellular Automaton; see later on for the definitions). In particular, on one hand we want to keep small the number of states (the first example of «small» CUCA is due to Smith III [13]; it requires 18 states); on the other hand we are interested into automata, possibly requiring a high number of states, whose transition law is «as simple as possible»; e.g. totalistic automata (the...
Some results on complexity of μ-calculus evaluation in the black-box model
We consider μ-calculus formulas in a normal form: after a prefix of fixed-point quantifiers follows a quantifier-free expression. We are interested in the problem of evaluating (model checking) such formulas in a powerset lattice. We assume that the quantifier-free part of the expression can be any monotone function given by a black-box – we may only ask for its value for given arguments. As a first result we prove that when the lattice is fixed, the problem becomes polynomial (the assumption about...
Some results on C-varieties
In an earlier paper, the second author generalized Eilenberg's variety theory by establishing a basic correspondence between certain classes of monoid morphisms and families of regular languages. We extend this theory in several directions. First, we prove a version of Reiterman's theorem concerning the definition of varieties by identities, and illustrate this result by describing the identities associated with languages of the form (a1a2...ak)+, where a1,...,ak are distinct letters. Next,...
Some results on finite maximal codes
Some results on the dot-depth hierarchy.
Some results on -varieties
In an earlier paper, the second author generalized Eilenberg’s variety theory by establishing a basic correspondence between certain classes of monoid morphisms and families of regular languages. We extend this theory in several directions. First, we prove a version of Reiterman’s theorem concerning the definition of varieties by identities, and illustrate this result by describing the identities associated with languages of the form , where are distinct letters. Next, we generalize the notions...
Some theorems on labelled bracketings used in transformational grammars
Some Thoughts on the Near-Future Digital Mathematics Library
The mathematicians’ Digital mathematics library (DML) summarises the generous project that all mathematics ever published should end up in digital form so that it would be more easily referenced, accessed, used. This concept was formulated at the very beginning of this century, and yielded a lot of international activity that culminated around years 2002–2005. While it is estimated that a substantial part of the existing math literature is already available in some digital format, nothing looking...
Some variants of Hausdorff distance for word matching
Some very effective methods of searching in tables
In this paper several methods for constructing tables without repetition of items are studied from the probabilstic point of view. Formulae for expected values of the number of examinations of the kind “is placed in cell in a table ?” are given. The situation when a table is placed on a backing store of a computer and segmented is also considered. Described methods are very useful in many systems of information processing.
Somme des chiffres et transcendance
Sorting with a forklift.