On codes having no finite completion
On coding morphisms for zigzag codes
On commutative Kleene monoids.
On computations with integer division
On conjugacy of languages
We say that two languages and are conjugates if they satisfy the conjugacy equation for some language . We study several problems associated with this equation. For example, we characterize all sets which are conjugated a two-element biprefix set , as well as all two-element sets which are conjugates.
On Conjugacy of Languages
We say that two languages X and Y are conjugates if they satisfy the conjugacy equationXZ = ZY for some language Z. We study several problems associated with this equation. For example, we characterize all sets which are conjugated via a two-element biprefix set Z, as well as all two-element sets which are conjugates.
On context constrained squares and repetitions in a string
On context-free rewriting with a simple restriction and its computational completeness
This paper discusses context-free rewriting systems in which there exist two disjoint finite sets of rules, and a symbol, referred to as a condition of applicability, is attached to each rule in either of these two sets. In one set, a rule with a symbol attached to it is applicable if the attached symbol occurs in the current rewritten string while in the other set, such a rule is applicable if the attached symbol does not occur there. The present paper demonstrates that these rewriting systems...
On Continued Fractions and Finite Automata.
On continuous functions computed by finite automata
On Convex Body Chasing.
On decidability of skeletal sets [Abstract of thesis]
On differentiation functions, structure functions, and related languages of context-free grammars
We introduce the notion of a differentiation function of a context-free grammar which gives the number of terminal words that can be derived in a certain number of steps. A grammar is called narrow (or -narrow) iff its differentiation function is bounded by a constant (by ). We present the basic properties of differentiation functions, especially we relate them to structure function of context-free languages and narrow grammars to slender languages. We discuss the decidability of the equivalence...
On differentiation functions, structure functions, and related languages of context-free grammars
We introduce the notion of a differentiation function of a context-free grammar which gives the number of terminal words that can be derived in a certain number of steps. A grammar is called narrow (or k-narrow) iff its differentiation function is bounded by a constant (by k). We present the basic properties of differentiation functions, especially we relate them to structure function of context-free languages and narrow grammars to slender languages. We discuss the decidability of ...
On directable automata
On distributive fixed-point expressions
On Distributive Fixed-Point Expressions
For every fixed-point expression e of alternation-depth r, we construct a new fixed-point expression e' of alternation-depth 2 and size . Expression e' is equivalent to e whenever operators are distributive and the underlying complete lattice has a co-continuous least upper bound. We alternation-depth but also w.r.t. the increase in size of the resulting expression.
On DOS languages and DOS mappings.
On dot-depth two
On equality sets of morphisms in topological free monoids