226 results on '"Partial word"'
Number of results to display per page
Search Results
2. Algebraic Aspects of Generalized Parikh Matrices on Partial Words.
- Author
-
Janaki, K., Krishna Kumari, R., Marichamy, S., Felixia, S., and Arulprakasam, R.
- Subjects
MATRICES (Mathematics) ,VOCABULARY ,ELECTRONIC noses - Abstract
In this paper, we extend the concept of a generalized Parikh vector of the partial word known as e--generalized Parikh vector, and its related properties are studied. We also introduce the e--generalized Parikh matrix of the partial word and provide its characterization theorem. Further, we discuss the algebraic properties of partial words in terms of e--generalized Parikh matrix. In addition, we define partial line languages and confer their properties concerning e--generalized Parikh vector of partial words. [ABSTRACT FROM AUTHOR]
- Published
- 2024
3. Repetitions in Toeplitz Words and the Thue Threshold
- Author
-
Boccuto, Antonio, Carpi, Arturo, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Anselmo, Marcella, editor, Della Vedova, Gianluca, editor, Manea, Florin, editor, and Pauly, Arno, editor
- Published
- 2020
- Full Text
- View/download PDF
4. AN ACCOUNT OF SPECIALITY OF PARTIALWORDS WITH RESPECT TO PERIODICITY.
- Author
-
Daisyjose, D., Arulprakasam, R., and Anuradha, A.
- Subjects
DNA - Abstract
A study on the behaviour of DNA strands lead to the introduction of the mathematical term 'partial word' by Berstel and Boasson and extended partial words with an arbitrary number of holes. The concept of a special partial word is crucial for these extensions. In this paper, we consider some cases on non-primitive partial words in which we have fixed the position of the hole and constructed a sequence of (k; l)-special for a fixed k where l varies. The periodicity is generalized for the considered partial words with the help of gcd(k; l) and it can be determined whether a partial word is (k; l)-special or not. [ABSTRACT FROM AUTHOR]
- Published
- 2022
5. Ternary Square-Free Partial Words with Many Wildcards
- Author
-
Gasnikov, Daniil, Shur, Arseny M., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Brlek, Srečko, editor, and Reutenauer, Christophe, editor
- Published
- 2016
- Full Text
- View/download PDF
6. Border Correlations, Lattices, and the Subgraph Component Polynomial
- Author
-
Blanchet-Sadri, Francine, Cordier, Michelle, Kirsch, Rachel, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Jan, Kratochvíl, editor, Miller, Mirka, editor, and Froncek, Dalibor, editor
- Published
- 2015
- Full Text
- View/download PDF
7. On the Language of Primitive Partial Words
- Author
-
Nayak, Ananda Chandra, Kapoor, Kalpesh, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Dediu, Adrian-Horia, editor, Formenti, Enrico, editor, Martín-Vide, Carlos, editor, and Truthe, Bianca, editor
- Published
- 2015
- Full Text
- View/download PDF
8. Polarization of neural codes.
- Author
-
CHRISTENSEN, Katie and KULOSMAN, Hamid
- Subjects
- *
NEURAL codes , *IDEALS (Algebra) , *RING theory , *PRIME ideals - Abstract
The neural rings and ideals as an algebraic tool for analyzing the intrinsic structure of neural codes were introduced by C. Curto, V. Itskov, A. Veliz-Cuba, and N. Youngs in 2013. Since then they were investigated in several papers, including the 2017 paper by S. Güntürkün, J. Jeffries, and J. Sun, in which the notion of polarization of neural ideals was introduced. In our paper we extend their ideas by introducing the notions of polarization of motifs and neural codes. We show that the notions that we introduce have very nice properties which allow the studying of the intrinsic structure of neural codes of length n via the square-free monomial ideals in 2n variables and interpreting the results back in the original neural code ambient space. In the last section of the paper we introduce the notions of inactive neurons, partial neural codes, and partial motifs, as well as the notions of polarization of these codes and motifs. We use these notions to give a new proof of a theorem from the paper by Güntürkün, Jeffries, and Sun that we mentioned above. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
9. Integer Vector Addition Systems with States
- Author
-
Haase, Christoph, Halfon, Simon, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Ouaknine, Joël, editor, Potapov, Igor, editor, and Worrell, James, editor
- Published
- 2014
- Full Text
- View/download PDF
10. Computing Depths of Patterns
- Author
-
Blanchet-Sadri, Francine, Lohr, Andrew, Simmons, Sean, Woodhouse, Brent, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dediu, Adrian-Horia, editor, Martín-Vide, Carlos, editor, Sierra-Rodríguez, José-Luis, editor, and Truthe, Bianca, editor
- Published
- 2014
- Full Text
- View/download PDF
11. Deciding Representability of Sets of Words of Equal Length in Polynomial Time
- Author
-
Blanchet-Sadri, Francine, Munteanu, Sinziana, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Lecroq, Thierry, editor, and Mouchard, Laurent, editor
- Published
- 2013
- Full Text
- View/download PDF
12. Strict Bounds for Pattern Avoidance
- Author
-
Blanchet-Sadri, Francine, Woodhouse, Brent, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Béal, Marie-Pierre, editor, and Carton, Olivier, editor
- Published
- 2013
- Full Text
- View/download PDF
13. Computing the Partial Word Avoidability Indices of Ternary Patterns
- Author
-
Blanchet-Sadri, Francine, Lohr, Andrew, Scott, Shane, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Arumugam, S., editor, and Smyth, W. F., editor
- Published
- 2012
- Full Text
- View/download PDF
14. Abelian Pattern Avoidance in Partial Words
- Author
-
Blanchet-Sadri, Francine, Simmons, Sean, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Rovan, Branislav, editor, Sassone, Vladimiro, editor, and Widmayer, Peter, editor
- Published
- 2012
- Full Text
- View/download PDF
15. Fine and Wilf’s Theorem for k-Abelian Periods
- Author
-
Karhumäki, Juhani, Puzynina, Svetlana, Saarela, Aleksi, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Yen, Hsu-Chun, editor, and Ibarra, Oscar H., editor
- Published
- 2012
- Full Text
- View/download PDF
16. Connecting Partial Words and Regular Languages
- Author
-
Dassow, Jürgen, Manea, Florin, Mercaş, Robert, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Cooper, S. Barry, editor, Dawar, Anuj, editor, and Löwe, Benedikt, editor
- Published
- 2012
- Full Text
- View/download PDF
17. Extending research on patterns in permutations and words to other domains
- Author
-
Kitaev, Sergey and Kitaev, Sergey
- Published
- 2011
- Full Text
- View/download PDF
18. Periods in Partial Words: An Algorithm
- Author
-
Blanchet-Sadri, Francine, Mandel, Travis, Sisodia, Gautam, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Iliopoulos, Costas S., editor, and Smyth, William F., editor
- Published
- 2011
- Full Text
- View/download PDF
19. Abelian Square-Free Partial Words
- Author
-
Blanchet-Sadri, Francine, Kim, Jane I., Mercaş, Robert, Severa, William, Simmons, Sean, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dediu, Adrian-Horia, editor, Fernau, Henning, editor, and Martín-Vide, Carlos, editor
- Published
- 2010
- Full Text
- View/download PDF
20. Avoidable Binary Patterns in Partial Words
- Author
-
Blanchet-Sadri, Francine, Mercaş, Robert, Simmons, Sean, Weissenstein, Eric, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dediu, Adrian-Horia, editor, Fernau, Henning, editor, and Martín-Vide, Carlos, editor
- Published
- 2010
- Full Text
- View/download PDF
21. Efficient enumeration of non-equivalent squares in partial words with few holes.
- Author
-
Charalampopoulos, Panagiotis, Crochemore, Maxime, Iliopoulos, Costas S., Kociumaka, Tomasz, Pissis, Solon P., Radoszewski, Jakub, Rytter, Wojciech, and Waleń, Tomasz
- Abstract
A word of the form WW for some word W∈Σ∗ is called a square. A partial word is a word possibly containing holes (also called don't cares). The hole is a special symbol ◊∉Σ which matches any symbol from Σ∪{◊}. A p-square is a partial word matching at least one square WW without holes. Two p-squares are called equivalent if they match the same set of squares. A p-square is called here unambiguous if it matches exactly one square WW without holes. Such p-squares are natural counterparts of classical squares. Let PSQUARESk(n) and USQUARESk(n) be the maximum number of non-equivalent p-squares and non-equivalent unambiguous p-squares in T over all partial words T of length n with at most k holes. We show asymptotically tight bounds: PSQUARESk(n)=Θ(min(nk2,n2)),USQUARESk(n)=Θ(nk).We present an algorithm that reports all non-equivalent p-squares in O(nk3) time for a partial word of length n with k holes, for an integer alphabet. In particular, it runs in linear time for k=O(1) and its time complexity near-matches the asymptotic bound for PSQUARESk(n). We also show an O(n)-time algorithm that reports all non-equivalent p-squares of a given length. The paper is a full and improved version of Charalampopoulos et al. (in Cao Y, Chen Y (eds) Proceedings of the 23rd international conference on computing and combinatorics, COCOON 2017; Springer, 2017). [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
22. Square-Free Partial Words with Many Wildcards.
- Author
-
Gasnikov, Daniil and Shur, Arseny M.
- Subjects
- *
VOCABULARY , *INFINITY (Mathematics) , *GENERALIZATION , *FLEXIBILITY (Mechanics) , *MATHEMATICAL proofs , *ESTIMATION theory - Abstract
We contribute to the study of square-free words. The classical notion of a square-free word has a natural generalization to partial words, studied in several papers since 2008. We prove that the maximal density of wildcards in the ternary infinite square-free partial word is surprisingly big: 3 / 1 6. Further we show that the density of wildcards in a finitary infinite square-free partial words is at most 1 / 3 and this bound is reached by a quaternary word. We demonstrate that partial square-free words can be viewed as “usual” square-free words with some letters replaced by wildcards and introduce the corresponding characteristic of infinite square-free words, called flexibility. The flexibility is estimated for some important words and classes of words; an interesting phenomenon is the existence of “rigid” square-free words, having no room for wildcards at all. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
23. Combinatorial Queries and Updates on Partial Words
- Author
-
Diaconu, Adrian, Manea, Florin, Tiseanu, Cătălin, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Kutyłowski, Mirosław, editor, Charatonik, Witold, editor, and Gębala, Maciej, editor
- Published
- 2009
- Full Text
- View/download PDF
24. How Many Holes Can an Unbordered Partial Word Contain?
- Author
-
Blanchet-Sadri, Francine, Allen, Emily, Byrum, Cameron, Mercaş, Robert, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Dediu, Adrian Horia, editor, Ionescu, Armand Mihai, editor, and Martín-Vide, Carlos, editor
- Published
- 2009
- Full Text
- View/download PDF
25. Open Problems on Partial Words
- Author
-
Blanchet-Sadri, Francine, Kacprzyk, Janusz, editor, Bel-Enguix, Gemma, editor, Jiménez-López, M. Dolores, editor, and Martín-Vide, Carlos, editor
- Published
- 2008
- Full Text
- View/download PDF
26. Relationally Periodic Sequences and Subword Complexity
- Author
-
Cassaigne, Julien, Kärki, Tomi, Zamboni, Luca Q., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Ito, Masami, editor, and Toyama, Masafumi, editor
- Published
- 2008
- Full Text
- View/download PDF
27. Watson-Crick Conjugate and Commutative Words
- Author
-
Kari, Lila, Mahalingam, Kalpana, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Garzon, Max H., editor, and Yan, Hao, editor
- Published
- 2008
- Full Text
- View/download PDF
28. Tiling Periodicity
- Author
-
Karhumäki, Juhani, Lifshits, Yury, Rytter, Wojciech, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Ma, Bin, editor, and Zhang, Kaizhong, editor
- Published
- 2007
- Full Text
- View/download PDF
29. Correlations of Partial Words
- Author
-
Blanchet-Sadri, Francine, Gafni, Joshua D., Wilson, Kevin H., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Rangan, C. Pandu, editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Thomas, Wolfgang, editor, and Weil, Pascal, editor
- Published
- 2007
- Full Text
- View/download PDF
30. Partial Words for DNA Coding
- Author
-
Leupold, Peter, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Ferretti, Claudio, editor, Mauri, Giancarlo, editor, and Zandron, Claudio, editor
- Published
- 2005
- Full Text
- View/download PDF
31. μo νo 2 πo λυ: Java-Based Conversion of Monotonic to Polytonic Greek
- Author
-
Likos, Johannis, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Syropoulos, Apostolos, editor, Berry, Karl, editor, Haralambous, Yannis, editor, Hughes, Baden, editor, Peter, Steven, editor, and Plaice, John, editor
- Published
- 2004
- Full Text
- View/download PDF
32. Covering problems for partial words and for indeterminate strings.
- Author
-
Crochemore, Maxime, Iliopoulos, Costas S., Kociumaka, Tomasz, Radoszewski, Jakub, Rytter, Wojciech, and Waleń, Tomasz
- Subjects
- *
DIOPHANTINE equations , *STRING theory , *PROBLEM solving , *DETERMINISTIC algorithms , *SET theory - Abstract
Indeterminate strings are a subclass of non-standard words having non-deterministic nature. In a classic string every position contains exactly one symbol—we say it is a solid symbol—while in an indeterminate string a position may contain a set of symbols (possible at this position); such sets are called non-solid symbols. The most important subclass of indeterminate strings are partial words, where each non-solid symbol is the whole alphabet; in this case non-solid symbols are also called don't care symbols. We consider the problem of finding a shortest cover of an indeterminate string, i.e., finding a shortest solid string whose occurrences cover the whole indeterminate string. We show that this classical problem becomes NP-complete for indeterminate strings and even for partial words. The proof of this fact is one of the main results of this paper. Our other main results focus on design of algorithms efficient with respect to certain parameters of the input (so called FPT algorithms) for the shortest cover problem. For the indeterminate string covering problem we obtain an O ( n k 2 + 2 k k 3 ) -time algorithm, where k is the number of non-solid symbols, while for the partial word covering problem we obtain a running time of O ( n k 2 + 2 O ( k log k ) ) . Additionally, we prove that, unless the Exponential Time Hypothesis is false, no 2 o ( k ) n O ( 1 ) -time solution exists for either problem, which shows that our algorithm for partial words is close to optimal. We also present an algorithm for both problems parameterized both by k and the alphabet size with a simple implementation. A preliminary version of this article was presented at the 25th International Symposium on Algorithms and Computation (ISAAC 2014), LNCS, vol. 8889, pp. 220–232, Springer (2014) [12] . [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
33. On universal partial words.
- Author
-
Chen, Herman Z.Q., Kitaev, Sergey, Mütze, Torsten, and Sun, Brian Y.
- Abstract
A universal word for a finite alphabet A and some integer n ≥ 1 is a word over A such that every word of length n appears exactly once as a (consecutive) subword. It is well-known and easy to prove that universal words exist for any A and n . In this work we initiate the systematic study of universal partial words. These are words that in addition to the letters from A may contain an arbitrary number of occurrences of a special ‘joker’ symbol ⋄ ∉ A , which can be substituted by any symbol from A . For example, u = 0 ⋄ 011100 is a universal partial word for the binary alphabet A = { 0 , 1 } and for n = 3 (e.g., the first three letters of u yield the subwords 000 and 010). We present results on the existence and non-existence of universal partial words in different situations (depending on the number of ⋄s and their positions), including various explicit constructions. We also provide numerous examples of universal partial words that we found with the help of a computer. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
34. Repetitions in Toeplitz Words and the Thue Threshold
- Author
-
Antonio Boccuto and Arturo Carpi
- Subjects
Partial word ,Sequence ,Euclidean space ,Existential quantification ,Word with bounded square ,Integer lattice ,Arithmetic subword ,Toeplitz matrix ,Article ,Toeplitz word ,Power-free word, Toeplitz word, partial word, word with bounded square, Thue threshold, arithmetic subword ,Combinatorics ,Power-free word ,Thue threshold ,Word (group theory) ,Integer (computer science) ,Mathematics - Abstract
A (finite or infinite) word is said to be k-th power-free if it does not contain k consecutive equal blocks. A colouring of the integer lattice points in the n-dimensional Euclidean space is power-free if there exists a positive integer k such that the sequence of colours of consecutive points on any straight line is a k-th power-free word. The Thue threshold of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb Z^n$$\end{document} is the least number of colours t(n) allowing a power-free colouring of the integer lattice points in the n-dimensional Euclidean space. Answering a question of Grytczuk (2008), we prove that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t(2)=t(3)=2$$\end{document}. Moreover, we show the existence of a 2-colouring of the integer lattice points in the Euclidean plane such that the sequence of colours of consecutive points on any straight line does not contain squares of length larger than 26. In order to obtain these results, we study repetitions in Toeplitz words. We show that the Toeplitz word generated by any sequence of primitive partial words of maximal length k is k-th power-free. Moreover, adding a suitable hypothesis on the positions of the holes in the generating sequence, we obtain that also the subwords occurring in the considered Toeplitz word according to an arithmetic progression of suitable difference, are k-th power-free words.
- Published
- 2020
35. Parallel composition and deadlocking
- Author
-
Goos, G., editor, Hartmanis, J., editor, and Vogler, W., editor
- Published
- 1992
- Full Text
- View/download PDF
36. Petri nets and their semantics
- Author
-
Goos, G., editor, Hartmanis, J., editor, and Vogler, W., editor
- Published
- 1992
- Full Text
- View/download PDF
37. Bisimulation and action refinement
- Author
-
Vogler, Walter, Goos, G., editor, Hartmanis, J., editor, Barstow, D., editor, Brauer, W., editor, Brinch Hansen, P., editor, Gries, D., editor, Luckham, D., editor, Moler, C., editor, Pnueli, A., editor, Seegmüller, G., editor, Stoer, J., editor, Wirth, N., editor, Choffrut, Christian, editor, and Jantzen, Matthias, editor
- Published
- 1991
- Full Text
- View/download PDF
38. Petri net systems and their closure properties
- Author
-
Kiehn, Astrid, Goos, G., editor, Hartmanis, J., editor, Barstow, D., editor, Brauer, W., editor, Brinch Hansen, P., editor, Gries, D., editor, Luckham, D., editor, Moler, C., editor, Pnueli, A., editor, Seegmüller, G., editor, Stoer, J., editor, Wirth, N., editor, and Rozenberg, Grzegorz, editor
- Published
- 1990
- Full Text
- View/download PDF
39. A note on the longest common compatible prefix problem for partial words.
- Author
-
Crochemore, M., Iliopoulos, C.S., Kociumaka, T., Kubica, M., Langiu, A., Radoszewski, J., Rytter, W., Szreder, B., and Waleń, T.
- Abstract
For a partial word w the longest common compatible prefix of two positions i , j , denoted lccp ( i , j ) , is the largest k such that w [ i , i + k − 1 ] and w [ j , j + k − 1 ] are compatible. The LCCP problem is to preprocess a partial word in such a way that any query lccp ( i , j ) about this word can be answered in O ( 1 ) time. We present a simple solution to this problem that works for any linearly-sortable alphabet. Our preprocessing is in time O ( n μ + n ) , where μ is the number of blocks of holes in w . [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
40. Detecting Deep-Fake Videos from Phoneme-Viseme Mismatches
- Author
-
Hany Farid, Maneesh Agrawala, Ohad Fried, and Shruti Agarwal
- Subjects
Focus (computing) ,Computer science ,business.industry ,Speech recognition ,Viseme ,Mouth shape ,GeneralLiterature_MISCELLANEOUS ,Computer graphics ,Robustness (computer science) ,Dynamics (music) ,Audio synthesis ,Partial word ,Artificial intelligence ,business - Abstract
Recent advances in machine learning and computer graphics have made it easier to convincingly manipulate video and audio. These so-called deep-fake videos range from complete full-face synthesis and replacement (face-swap), to complete mouth and audio synthesis and replacement (lip-sync), and partial word-based audio and mouth synthesis and replacement. Detection of deep fakes with only a small spatial and temporal manipulation is particularly challenging. We describe a technique to detect such manipulated videos by exploiting the fact that the dynamics of the mouth shape - visemes - are occasionally inconsistent with a spoken phoneme. We focus on the visemes associated with words having the sound M (mama), B (baba), or P (papa) in which the mouth must completely close in order to pronounce these phonemes. We observe that this is not the case in many deep-fake videos. Such phoneme-viseme mismatches can, therefore, be used to detect even spatially small and temporally localized manipulations. We demonstrate the efficacy and robustness of this approach to detect different types of deep-fake videos, including in-the-wild deep fakes.
- Published
- 2020
- Full Text
- View/download PDF
41. Semantic relation classification through low-dimensional distributed representations of partial word sequences
- Author
-
Chihiro Shibata, Zhan Jin, and Kazuya Tago
- Subjects
Nonlinear classifier ,Artificial neural network ,business.industry ,Computer science ,Dimensionality reduction ,Partial word ,Artificial intelligence ,Language model ,business ,computer.software_genre ,computer ,Natural language processing ,Semantic relation - Published
- 2019
- Full Text
- View/download PDF
42. Partial word order freezing in Dutch
- Author
-
Petra Hendriks and Gerlof Bouma
- Subjects
Linguistics and Language ,Object (grammar) ,computer.software_genre ,050105 experimental psychology ,Definiteness ,Subject (grammar) ,Computer Science (miscellaneous) ,Department Linguistik ,0501 psychology and cognitive sciences ,Mathematics ,060201 languages & linguistics ,business.industry ,05 social sciences ,06 humanities and the arts ,Optimality theory ,16. Peace & justice ,Linguistics ,Philosophy ,Variation (linguistics) ,0602 languages and literature ,Partial word ,Artificial intelligence ,ddc:004 ,ddc:400 ,business ,computer ,Natural language processing ,Sentence ,Word order - Abstract
Dutch allows for variation as to whether the first position in the sentence is occupied by the subject or by some other constituent, such as the direct object. In particular situations, however, this commonly observed variation in word order is `frozen' and only the subject appears in first position. We hypothesize that this partial freezing of word order in Dutch can be explained from the dependence of the speaker's choice of word order on the hearer's interpretation of this word order. A formal model of this interaction between the speaker's perspective and the hearer's perspective is presented in terms of bidirectional Optimality Theory. Empirical predictions of this model regarding the interaction between word order and definiteness are confirmed by a quantitative corpus study.
- Published
- 2020
43. Computing longest common extensions in partial words
- Author
-
S. Osborne and Francine Blanchet-Sadri
- Subjects
Discrete mathematics ,Applied Mathematics ,String (computer science) ,Context (language use) ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Substring ,Longest repeated substring problem ,Longest common substring problem ,Combinatorics ,Combinatorics on words ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,020201 artificial intelligence & image processing ,Partial word ,Word (group theory) ,Mathematics - Abstract
The Longest Common Extension of a pair of positions ( i , j ) in a string, or word, is the longest substring starting at i and j . The LCE problem considers a word and a set of pairs of positions and computes for each pair in the set, the longest common extension starting at both positions in the pair. This problem finds applications in matching with don’t-care characters, approximate string searching, finding all exact or approximate tandem repeats, to name a few. From a practical point of view, Ilie et al. (Journal of Discrete Algorithms, 2010) looked for simple and efficient algorithms for the LCE problem. In this paper, we extend their analyses to partial words, strings with don’t-cares or holes. We compute the Longest Common Compatible Extension of each pair of positions ( i , j ) in a partial word, i.e., the longest substrings starting at i and j that are compatible via a combinatorial approach. We also estimate the LCCE of each pair of positions in a partial word via a probabilistic approach. We show that our results match with those of total words (partial words without holes). We find that one of the simplest algorithms for implementing the LCE problem is optimal on average in the context of partial words.
- Published
- 2018
- Full Text
- View/download PDF
44. Square-Free Partial Words with Many Wildcards
- Author
-
Arseny M. Shur and Daniil Gasnikov
- Subjects
Square-free word ,Generalization ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,Wildcard character ,0102 computer and information sciences ,02 engineering and technology ,Square-free integer ,computer.file_format ,01 natural sciences ,Combinatorics ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Computer Science (miscellaneous) ,Finitary ,020201 artificial intelligence & image processing ,Partial word ,computer ,Computer Science::Formal Languages and Automata Theory ,Word (group theory) ,Mathematics - Abstract
We contribute to the study of square-free words. The classical notion of a square-free word has a natural generalization to partial words, studied in several papers since 2008. We prove that the maximal density of wildcards in the ternary infinite square-free partial word is surprisingly big: [Formula: see text]. Further we show that the density of wildcards in a finitary infinite square-free partial words is at most [Formula: see text] and this bound is reached by a quaternary word. We demonstrate that partial square-free words can be viewed as “usual” square-free words with some letters replaced by wildcards and introduce the corresponding characteristic of infinite square-free words, called flexibility. The flexibility is estimated for some important words and classes of words; an interesting phenomenon is the existence of “rigid” square-free words, having no room for wildcards at all.
- Published
- 2018
- Full Text
- View/download PDF
45. Two equational theories of partial words
- Author
-
Christian Choffrut and Zoltán Ésik
- Subjects
Pure mathematics ,General Computer Science ,Series (mathematics) ,Closure (topology) ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Theoretical Computer Science ,Decidability ,010201 computation theory & mathematics ,Simple (abstract algebra) ,Product (mathematics) ,0202 electrical engineering, electronic engineering, information engineering ,Order (group theory) ,020201 artificial intelligence & image processing ,Partial word ,Isomorphism ,Mathematics - Abstract
Partial words are in our terminology isomorphism classes of labeled partial orders. We consider two structures. Starting with the partial orders reduced to a unique element, the first one is defined as the closure under the three operations of series product, parallel product and ω-power (ω-series product of the same partial word) and the second one as the closure under the three operations of series product, parallel product and ω-product (ω-series product of possibly different partial words). We show that the two equational theories can be axiomatized by an infinite collection of simple identities, and that no finite axiomatization exists. We characterize the free algebras in the corresponding varieties as algebras of certain partial words subject to order and graph theoretic conditions. We also show that the first equational theory is decidable.
- Published
- 2018
- Full Text
- View/download PDF
46. Several extensions of the Parikh matrix L-morphism
- Author
-
Alazemi, Hamed M.K. and Černý, Anton
- Subjects
- *
MATHEMATIC morphism , *MATHEMATICAL mappings , *POLYNOMIALS , *MATRICES (Mathematics) , *FUZZY systems , *MATHEMATICAL analysis - Abstract
Abstract: The Parikh matrix mapping is a morphism assigning to each word w over a k-letter alphabet a upper triangular matrix with entries expressing the number of occurrences in w of some specific subwords. To tackle the problem of ambiguity of this mapping two new mappings have been proposed in literature, assigning to words matrices with polynomial entries (q-matrices). One is a more subtle, but still ambiguous morphism, the other is unambiguous but not a morphism. We show that the former mapping can be extended to match even a fairly general extension of the original Parikh matrix morphism. Then we introduce an unambiguous q-matrix morphism based on the same general Parikh matrix mapping. Finally, we consider the problem of incomplete information on word symbols and show that the general Parikh matrix mapping can be further extended to deal with counts of fuzzy subword occurrences. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
47. Border correlations, lattices, and the subgraph component polynomial
- Author
-
Rachel Kirsch, Michelle Cordier, and Francine Blanchet-Sadri
- Subjects
Connected component ,Vertex (graph theory) ,Discrete mathematics ,Polynomial ,Binary number ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Set (abstract data type) ,Combinatorics ,Distributive property ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,020201 artificial intelligence & image processing ,Partial word ,Word (group theory) ,Mathematics - Abstract
We consider the border sets of partial words and study the combinatorics of specific representations of them, called border correlations, which are binary vectors of same length indicating the borders. We characterize precisely which of these vectors are valid border correlations, and establish a one-to-one correspondence between the set of valid border correlations and the set of valid ternary period correlations of a given length, the latter being ternary vectors representing the strong and strictly weak period sets. It turns out that the sets of all border correlations of a given length form distributive lattices under suitably defined partial orderings. We also give connections between the ternary period correlation of a partial word and its refined border correlation which specifies the lengths of all the word’s bordered cyclic shifts’ minimal borders. Finally, we investigate the population size, that is, the number of partial words sharing a given (refined) border correlation, and obtain formulas to compute it. We do so using the subgraph component polynomial of an undirected graph, introduced recently by Tittmann et al. (2011), which counts the number of connected components in vertex induced subgraphs.
- Published
- 2018
- Full Text
- View/download PDF
48. Computing primitively-rooted squares and runs in partial words
- Author
-
Xufan Zhang, Justin Lazarow, Francine Blanchet-Sadri, Jordan Nikkel, and J.D. Quigley
- Subjects
Sequence ,Wildcard character ,0102 computer and information sciences ,02 engineering and technology ,computer.file_format ,01 natural sciences ,Substring ,Combinatorics ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,020201 artificial intelligence & image processing ,Partial word ,Alphabet ,computer ,Computer Science::Formal Languages and Automata Theory ,Mathematics - Abstract
This paper deals with two types of repetitions in strings: squares, which consist of two adjacent occurrences of substrings, and runs, which are periodic substrings that cannot be extended further to the left or right while maintaining the period. We show how to compute all the primitively-rooted squares in a given partial word, which is a sequence that may have undefined positions, called holes or wildcards, that match any letter of the alphabet over which the sequence is defined. We also describe an algorithm for computing all primitively-rooted runs in a given partial word and extend previous analyses on the number of runs to partial words.
- Published
- 2018
- Full Text
- View/download PDF
49. A NEW PROOF OF THE THREE-SQUARES LEMMA FOR PARTIAL WORDS WITH ONE HOLE.
- Author
-
KÄRKI, TOMI and Salomaa, Arto
- Subjects
- *
COMPUTATIONAL linguistics , *MATHEMATICAL proofs , *FACTORS (Algebra) , *SQUARE , *PROOF theory , *MATHEMATICAL formulas , *MATHEMATICAL analysis - Abstract
In this paper we give a new proof and a small improvement for the three-squares lemma for partial words with one hole. This recent result by Blanchet-Sadri et al. gives a lower bound for the length of the longest square in the situation where three squares begin at the same position of a one-hole word and the shortest square satisfies a primitivity condition. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
50. FINE AND WILF'S THEOREM FOR PARTIAL WORDS WITH ARBITRARILY MANY WEAK PERIODS.
- Author
-
BLANCHET-SADRI, F., OEY, TAKTIN, RANKIN, TIMOTHY D., Csuhaj-Varjú, Erzsébet, and Ésik, Zoltán
- Subjects
- *
COMPUTER science , *FORMAL languages , *COMPUTATIONAL biology , *ELECTRONIC data processing , *DATA compression , *MATHEMATICAL sequences , *ALGORITHMS , *COMBINATORICS - Abstract
Fine and Wilf's well-known theorem states that any word having periods p,q and length at least p+q-gcd(p,q) also has gcd(p,q) as a period. Moreover, the length p+q-gcd(p,q) is critical since counterexamples can be provided for shorter words. This result has since been extended to partial words, or finite sequences that may contain some "holes." More precisely, any partial word u with H holes having weak periods p,q and length at least the so-denoted lH(p,q) also has strong period gcd(p,q) provided u is not (H,(p,q))-special. This extension was done for one hole by Berstel and Boasson (where the class of (1,(p,q))-special partial words is empty), and for an arbitrary number of holes by Blanchet-Sadri. In this paper, we further extend these results, allowing an arbitrary number of weak periods. In addition to speciality, the concepts of intractable period sets and interference between periods play a role. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
Catalog
Books, media, physical & digital resources
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.