Some closure properties of the nondeterministic regular translations.
Some consequences of a result of Ehrenfeucht and Rozenberg
Some further remarks on the family of finite index matrix languages
Some further remarks on the index of context-free languages
Some problems in automata theory which depend on the models of set theory
We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system ZFC. It is known that there are only three possibilities for the cardinality of the complement of an ω-language L(x1d49c;) accepted by a Büchi 1-counter automaton x1d49c;. We prove the following surprising result: there exists a 1-counter Büchi automaton x1d49c; such that the cardinality of the complement L(𝒜) − of the ω-language L(𝒜) is not determined...
Some problems in automata theory which depend on the models of set theory
We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system ZFC. It is known that there are only three possibilities for the cardinality of the complement of an ω-language L(𝒜) accepted by a Büchi 1-counter automaton 𝒜. We prove the following surprising result: there exists a 1-counter Büchi automaton 𝒜 such that the cardinality of the complement L(𝒜) − of the ω-language L(𝒜) is not determined by ZFC: (1) There is a model V1...
Some problems in modelling of real systems by formalized ones
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 on finite maximal codes
Some results on the dot-depth hierarchy.
Some theorems on labelled bracketings used in transformational grammars
Space classes, intersection of languages and bounded erasing homomorphisms
Spezielle Gleichungen in freien Halbgruppen und eine Anwendung auf Normalformen regulärer Ereignisse
Square-free and overlap-free words
Squares and overlaps in the Thue-Morse sequence and some variants
We consider the position and number of occurrences of squares in the Thue-Morse sequence, and show that the corresponding sequences are 2-regular. We also prove that changing any finite but nonzero number of bits in the Thue-Morse sequence creates an overlap, and any linear subsequence of the Thue-Morse sequence (except those corresponding to decimation by a power of 2) contains an overlap.
Stackautomaten in Labyrinthen.
State complexity of cyclic shift
The cyclic shift of a language , defined as =, is an operation known to preserve both regularity and context-freeness. Its descriptional complexity has been addressed in Maslov’s pioneering paper on the state complexity of regular language operations [Soviet Math. Dokl. 11 (1970) 1373–1375], where a high lower bound for partial DFAs using a growing alphabet was given. We improve this result by using a fixed 4-letter alphabet, obtaining a lower bound (n-1)! 2, which shows that the state complexity...
State complexity of cyclic shift
The cyclic shift of a language L, defined as SHIFT(L) = {vu | uv ∈ L}, is an operation known to preserve both regularity and context-freeness. Its descriptional complexity has been addressed in Maslov's pioneering paper on the state complexity of regular language operations [Soviet Math. Dokl.11 (1970) 1373–1375], where a high lower bound for partial DFAs using a growing alphabet was given. We improve this result by using a fixed 4-letter alphabet, obtaining a lower bound (n-1)! . 2(n-1)(n-2), which...