For any finite word on a finite alphabet, we consider the basic parameters and of defined as follows: is the minimal natural number for which has no right special factor of length and is the minimal natural number for which has no repeated suffix of length . In this paper we study the distributions of these parameters, here called characteristic parameters, among the words of each length on a fixed alphabet.
For any finite word w on a finite alphabet, we consider the basic parameters Rw and Kw of w defined as follows: Rw is the minimal natural number for which w has no right special factor of length Rw and Kw is the minimal natural number for which w has no repeated suffix of length Kw. In this paper we study the distributions of these parameters, here called characteristic parameters, among the words of each length on a fixed alphabet.
The characteristic parameters and of a word over a finite alphabet are defined as follows: is the minimal natural number such that has no repeated suffix of length and is the minimal natural number such that has no right special factor of length . In a previous paper, published on this journal, we have studied the distributions of these parameters, as well as the distribution of the maximal length of a repetition, among the words of each length on a given alphabet. In this paper...
The characteristic parameters Kw and Rw of a word w over a finite alphabet are defined as follows: Kw is the minimal natural number such that w has no repeated suffix of length Kw and Rw is the minimal natural number such that w has no right special factor of length Rw. In a previous paper, published on this journal, we have studied the distributions of these parameters, as well as the distribution of the maximal length of a repetition, among the words of each length on a given alphabet....
The He matrix, put forward by He and He in 1989, is designed as a means for uniquely representing the structure of a hexagonal system (= benzenoid graph). Observing that the He matrix is just the adjacency matrix of a pertinently weighted inner dual of the respective hexagonal system, we establish a number of its spectral properties. Afterwards, we discuss the number of eigenvalues equal to zero of the He matrix of a hexagonal system. Moreover, we obtain a relation between the number of triangles...
This paper establishes computational equivalence of two seemingly unrelated concepts: linear conjunctive grammars and trellis automata. Trellis automata, also studied under the name of one-way real-time cellular automata, have been known since early 1980s as a purely abstract model of parallel computers, while linear conjunctive grammars, introduced a few years ago, are linear context-free grammars extended with an explicit intersection operation. Their equivalence implies the equivalence of several...
This paper establishes computational equivalence of two seemingly unrelated concepts: linear conjunctive grammars and trellis automata. Trellis automata, also studied under the name of one-way real-time cellular automata, have been known since early 1980s as a purely abstract model of parallel computers, while linear conjunctive grammars, introduced a few years ago, are linear context-free grammars extended with an explicit intersection operation. Their equivalence implies the equivalence of several...
We investigate the complexity of languages described by some expressions containing shuffle operator and intersection. We show that deciding whether the shuffle of two words has a nonempty intersection with a regular set (or fulfills some regular pattern) is NL-complete. Furthermore we show that the class of languages of the form , with a shuffle language and a regular language , contains non-semilinear languages and does not form a family of mildly context- sensitive languages.
We investigate the complexity of languages described by some expressions containing shuffle operator and intersection. We show that deciding whether the shuffle of two words has a nonempty intersection with a regular set (or fulfills some regular pattern) is NL-complete. Furthermore we show that the class of languages of the form , with a shuffle language L and a regular language R, contains non-semilinear languages and does not form a family of mildly context- sensitive languages.