A note on equal powers of word morphisms
A note on exponential density of ETOL languages
A note on f-disjunctive languages.
A note on Glushkov's algorithm of the synthesis of finite automata
A note on grammars with regular restrictions
A note on homomorphisms of a free monoid.
A note on NSPACE () and substitution
A note on r-extensible prefix codes.
A note on the iteration of infinite matrices
A note on the minimalization of tree-automata
A note on the paper “disjunctive languages and compatible orders”
A note on the recognition of one counter languages
A note on the undecidability of contextfreeness
A note on van Wijngaarden syntax
A note on -rules in context-free grammars
A parenthesis machine for string manipulation
A perfect hashing incremental scheme for unranked trees using pseudo-minimal automata
We describe a technique that maps unranked trees to arbitrary hash codes using a bottom-up deterministic tree automaton (DTA). In contrast to other hashing techniques based on automata, our procedure builds a pseudo-minimal DTA for this purpose. A pseudo-minimal automaton may be larger than the minimal one accepting the same language but, in turn, it contains proper elements (states or transitions which are unique) for every input accepted by the automaton. Therefore, pseudo-minimal DTA...
A periodicity property of iterated morphisms
Suppose ƒ : X* → X* is a morphism and u,v ∈ X*. For every nonnegative integer n, let zn be the longest common prefix of ƒn(u) and ƒn(v), and let un,vn ∈ X* be words such that ƒn(u) = znun and ƒn(v) = znvn. We prove that there is a positive integer q such that for any positive integer p, the prefixes of un (resp. vn) of length p form an ultimately periodic sequence having period q. Further, there is a value of q which works for all words u,v ∈ X*.
A planar test of linguistic projectivity
A probabilistic approach to automaton-environment systems