PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 8

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  subword
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote Parikh Matrices and Parikh Rewriting Systems
Teh W. C.
Fundamenta Informaticae
|
2016
|
Vol. 146, nr 3
305--320
EN
Since the introduction of the Parikh matrix mapping, its injectivity problem is on top of the list of open problems in this topic. In 2010 Salomaa provided a solution for the ternary alphabet in terms of a Thue system with an additional feature called counter. This paper proposes the notion of a Parikh rewriting system as a generalization and systematization of Salomaa’s result. It will be shown that every Parikh rewriting system induces a Thue system without counters that serves as a feasible solution to the injectivity problem.
2
Content available remote The Computational Complexity of Universality Problems for Prefixes, Suffixes, Factors, and Subwords of Regular Languages
Rampersad N., Shallit J., Xu Z.
Fundamenta Informaticae
|
2012
|
Vol. 116, nr 1-4
223-236
EN
In this paper we consider the computational complexity of the following problems: given a DFA or NFA representing a regular language L over a finite alphabet Σ, is the set of all prefixes (resp., suffixes, factors, subwords) of all words of L equal to Σ*? In the case of testing universality for factors of languages, there is a connection to two classic problems: the synchronizing words problem of Černy, and Restivo's conjecture on the minimal uncompletable word.
3
Content available remote On the State Complexity of Scattered Substrings and Superstrings
Okhotin A.
Fundamenta Informaticae
|
2010
|
Vol. 99, nr 3
325-338
EN
It is proved that the set of scattered substrings of a language recognized by an n-state DFA requires a DFA with at least [formula] states (the known upper bound is 2*n), with witness languages given over an exponentially growing alphabet. For a 3-letter alphabet, scattered substrings are shown to require at least [formula] states. A similar state complexity function for scattered superstrings is determined to be exactly 2*(n-2) + 1 for an alphabet of at least n -2 letters, and strictly less for any smaller alphabet. For a 3-letter alphabet, the state complexity of scattered superstrings is at least [formula]
4
Content available remote Subword Balance in Binary Words, Languages and Sequences
Salomaa A.
Fundamenta Informaticae
|
2007
|
Vol. 75, nr 1-4
4690482-4690482
EN
We investigate binary words and languages having a balanced structure of (scattered) subwords. We introduce a "difference function" D for binary words. For D=0, the resulting language is properly context-sensitive. Parikh matrices constitute a useful technical tool in the study, we investigate also the independence of their entries. The investigation is extended to concern w-words and periodicity. For the Fibonacci word, the D-values are in many ways connected with the Fibonacci numbers.
5
Content available remote On Some Problems of Mateescu Concerning Subword Occurrences
Ding C., Salomaa A.
Fundamenta Informaticae
|
2006
|
Vol. 73, nr 1-2
65-79
EN
The paper investigates inference based on quantities |w|u, the number of occurrences of a word u as a scattered subword of w. Parikh matrices recently introduced are useful tools for such investigations. We introduce and study universal languages for Parikh matrices. We also obtain results concerning the inference from numbers |w|u to w, as well as from certain entries of a Parikh matrix to other entries.
6
Content available remote Injectivity of the Parikh Matrix Mappings Revisited
Serbanuta V.N., Serbanuta T.F.
Fundamenta Informaticae
|
2006
|
Vol. 73, nr 1-2
265-283
EN
We deal with the notion of M-unambiguity [5] in connection with the Parikh matrix mapping introduced by Mateescu and others in [7]. M-unambiguity is studied both in terms of words and matrices and several sufficient criteria for M-unambiguity are provided in both cases, nontrivially generalizing the criteria based on the g-property introduced by Salomaa in [15]. Also, the notion of M-unambiguity with respect to a word is defined in connection with the extended Parikh matrix morphism [16] and some of the M-unambiguity criteria are lifted from the classical setting to the extended one.
7
Content available remote On the Injectivity of Parikh Matrix Mappings
Salomaa A.
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
391-404
EN
We investigate the number of (scattered) subword occurrences and Parikh matrices, especially the case where the matrix determines the word uniquely. A condition introduced in this paper, called g-property, turns out to be a powerful tool for such unambiguous matrices. Interconnections with the general theory of subword histories are also pointed out.
8
Content available remote Subwords and power-free words are not expressible by word equations
Ilie L.
Fundamenta Informaticae
|
1999
|
Vol. 38, Nr 1,2
109-118
EN
We consider several open problems of Karhumäki, Mignosi and Plandowski, cf. [KMP], con-cerning the expressibility of languages and relations as solutions of word equations. We show first that the (scattered) subword relation is not expressible. Then, we consider the set of k-power-free finite words and solve it negatively for all nontrivial integer values of k. Finally, we consider the Fibonacci finite words. We do not solve the problem of the expressibility of the set of these words but prove that a negative answer (as believed) cannot be given using the tools in [KMP].
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.