This paper discusses path controlled grammars—context-free gram-
mars with a root-to-leaf path in their derivation trees restricted by a control
language. First, it investigates the impact of erasing rules on the generative
power of path controlled grammars. Then, it establishes two Chomsky-like
normal forms for path controlled grammars—the first allows unit rules, the
second allows just one erasing rule.

The paper summarizes properties of topological and sequence en- tropy of the Morse shift X_M generated by the Thue-Morse sequence t_M. The first part is an estimation of growth rate of possible subwords in t_M. We show a polynomial upper bound on the number of finite subwords occuring in t_M which is Cn^2log3 for some constant C > 0. In the second part we prove that the sequence entropy of X_M is achieved for the sequence  r(i) = 2²ⁱ − 1.

Various kinds of decipherability of codes, weaker than unique de- cipherability, have been studied since mid-1980s. We consider decipherability of directed figure codes, where directed figures are defined as labelled polyomi- noes with designated start and end points, equipped with catenation operation that may use a merging function to resolve possible conflicts. This setting ex- tends decipherability questions from words to 2D structures. In the present paper we develop a (variant of) domino graph that will allow us to decide some of the decipherability kinds by searching the graph for specific paths. Thus the main result characterizes directed figure decipherability by graph properties.

In a Cantor metric space B^Z, we present a one-sided cellular
automaton which positively answers the question
Does it exist a transitive cellular automaton (B^Z, F) with non-empty set of
strictly temporally periodic points?
The question can be found in a current and recognized literature of the subject.

This paper presents new grammar systems that describe transfor- mations of syntactic structures. They represent two approaches: synchronous grammars and transducers. The systems consist of well-known models such as context-free grammars and finite automata. Particular attention is paid to synchronization of regulated grammars. The paper recalls formal definitions of the systems and discusses theoretical results regarding their generative and accepting power. The last part briefly introduces application perspectives in natural language translation, illustrated by examples of Czech-English translation.