Search

Your search keyword '"KARHUMÄKI, JUHANI"' showing total 965 results
Start Over Author "KARHUMÄKI, JUHANI"

Refine your results

more »

more »

more »

more »
965 results on '"KARHUMÄKI, JUHANI"'

2. On Abelian Closures of Infinite Non-binary Words

Author

Karhumäki, Juhani, Puzynina, Svetlana, and Whiteland, Markus A.

Subjects
Mathematics - Combinatorics, Computer Science - Formal Languages and Automata Theory
Abstract

Two finite words $u$ and $v$ are called abelian equivalent if each letter occurs equally many times in both $u$ and $v$. The abelian closure $\mathcal{A}(\mathbf{x})$ of an infinite word $\mathbf{x}$ is the set of infinite words $\mathbf{y}$ such that, for each factor $u$ of $\mathbf{y}$, there exists a factor $v$ of $\mathbf{x}$ which is abelian equivalent to $u$. The notion of an abelian closure gives a characterization of Sturmian words: among uniformly recurrent binary words, periodic and aperiodic Sturmian words are exactly those words for which $\mathcal{A}(\mathbf{x})$ equals the shift orbit closure $\Omega(\mathbf{x})$. Furthermore, for an aperiodic binary word that is not Sturmian, its abelian closure contains infinitely many minimial subshifts. In this paper we consider the abelian closures of well-known families of non-binary words, such as balanced words and minimal complexity words. We also consider abelian closures of general subshifts and make some initial observations of their abelian closures and pose some related open questions.

Published
2020

3. On cardinalities of $k$-abelian equivalence classes

Author

Karhumäki, Juhani, Puzynina, Svetlana, Rao, Michaël, and Whiteland, Markus A.

Subjects
Mathematics - Combinatorics, Computer Science - Discrete Mathematics
Abstract

Two words $u$ and $v$ are $k$-abelian equivalent if, for each word $x$ of length at most $k$, $x$ occurs equally many times as a factor in both $u$ and $v$. The notion of $k$-abelian equivalence is an intermediate notion between the abelian equivalence and the equality of words. In this paper, we study the equivalence classes induced by the $k$-abelian equivalence, mainly focusing on the cardinalities of the classes. In particular, we are interested in the number of singleton $k$-abelian classes, i.e., classes containing only one element. We find a connection between the singleton classes and cycle decompositions of the de Bruijn graph. We show that the number of classes of words of length $n$ containing one single element is of order $\mathcal O(n^{N_m(k-1)-1})$, where $N_m(l) = \tfrac{1}{l}\sum_{d\mid l} \varphi(d)m^{l/d}$ is the number of necklaces of length $l$ over an $m$-ary alphabet. We conjecture that the upper bound is sharp. We also remark that, for $k$ even and $m = 2$, the lower bound $\Omega(n^{N_m(k-1)-1})$ follows from an old conjecture on the existence of Gray codes for necklaces of odd length. We verify this conjecture for necklaces of length up to 15., Comment: 21 pages, 4 figures, 2 tables

Published
2016

4. Testing k-binomial equivalence

Author

Freydenberger, Dominik D., Gawrychowski, Pawel, Karhumäki, Juhani, Manea, Florin, and Rytter, Wojciech

Subjects
Computer Science - Formal Languages and Automata Theory
Abstract

Two words $w_1$ and $w_2$ are said to be $k$-binomial equivalent if every non-empty word $x$ of length at most $k$ over the alphabet of $w_1$ and $w_2$ appears as a scattered factor of $w_1$ exactly as many times as it appears as a scattered factor of $w_2$. We give two different polynomial-time algorithms testing the $k$-binomial equivalence of two words. The first one is deterministic (but the degree of the corresponding polynomial is too high) and the second one is randomised (it is more direct and more efficient). These are the first known algorithms for the problem which run in polynomial time.

Published
2015

5. On maximal chains of systems of word equations

Author

Karhumäki, Juhani and Saarela, Aleksi

Subjects
Mathematics - Combinatorics, 68R15
Abstract

We consider systems of word equations and their solution sets. We discuss some fascinating properties of those, namely the size of a maximal independent set of word equations, and proper chains of solution sets of those. We recall the basic results, extend some known results and formulate several fundamental problems of the topic., Comment: 10 pages. This is a journal article published in 2011, together with a note about a missing reference added in 2015

Published
2015
Full Text
View/download PDF

8. Variations of the Morse-Hedlund Theorem for $k$-Abelian Equivalence

Author

Karhumäki, Juhani, Saarela, Aleksi, and Zamboni, Luca. Q.

Subjects
Mathematics - Combinatorics, 68R15
Abstract

In this paper we investigate local to global phenomena for a new family of complexity functions of infinite words indexed by $k \in \Ni \cup \{+\infty\}$ where $\Ni$ denotes the set of positive integers. Two finite words $u$ and $v$ in $A^*$ are said to be $k$-Abelian equivalent if for all $x \in A^*$ of length less than or equal to $k$, the number of occurrences of $x$ in $u$ is equal to the number of occurrences of $x$ in $v$. This defines a family of equivalence relations $\sim_k$ on $A^*$, bridging the gap between the usual notion of Abelian equivalence (when $k = 1$) and equality (when $k = +\infty$). Given an infinite word $w \in A^\omega$, we consider the associated complexity function $\mathcal P^{(k)}_w : \Ni \rightarrow \Ni$ which counts the number of $k$-Abelian equivalence classes of factors of $w$ of length $n$. As a whole, these complexity functions have a number of common features: Each gives a characterization of periodicity in the context of bi-infinite words, and each can be used to characterize Sturmian words in the framework of aperiodic one-sided infinite words. Nevertheless, they also exhibit a number of striking differences, the study of which is one of the main topics of our paper.

Published
2013

9. On Abelian Subshifts

Author

Karhumäki, Juhani, Puzynina, Svetlana, Whiteland, Markus A., 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, Hoshi, Mizuho, editor, and Seki, Shinnosuke, editor

Published
2018
Full Text
View/download PDF

10. Regularity of k-Abelian Equivalence Classes of Fixed Cardinality

Author

Karhumäki, Juhani, Whiteland, Markus A., 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, Böckenhauer, Hans-Joachim, editor, Komm, Dennis, editor, and Unger, Walter, editor

Published
2018
Full Text
View/download PDF

11. Observations and Problems on k-abelian avoidability

Author

Huova, Mari and Karhumäki, Juhani

Subjects
Mathematics - Combinatorics, 68R15
Abstract

We introduce new avoidability problems for words by considering equivalence relations, k-abelian equivalences, which lie properly in between equality and commutative equality, i.e. abelian equality. For two k-abelian equivalent words the numbers of occurrences of different factors of length k coincide and the prefixies (resp. suffixies) of length k-1 are equal as well. The size of the smallest alphabet avoiding 2-repetitions of words, i.e. squares, is three and for abelian squares it is four. It follows that for 2-abelian squares this size has to be three or four. Similarly, the size of the smallest alphabet where 2-abelian cubes, i.e. 3-repetitions, can be avoided is two or three, because cubes (resp. abelian cubes) are avoidable in binary (resp. ternary) alphabet. We show that for 2-abelian squares the required size is four, as in the case of abelian squares. The longest 2-abelian square-free ternary word is of length 537. The question for 2-abelian cubes is open. Though, we have computational evidence that the size would be two, since there exists 2-abelian cube-free binary word of length 100 000, meaning that the 2-abelian case would behave like that of words., Comment: 6 pages, 3 figures, Dagstuhl Seminar Combinatorial and Algorithmic Aspects of Sequence Processing (11081)

Published
2011

14. k-Abelian Equivalence and Rationality

Author

Cassaigne, Julien, Karhumäki, Juhani, Puzynina, Svetlana, Whiteland, Markus A., 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

15. Degrees of Infinite Words, Polynomials and Atoms

Author

Endrullis, Jörg, Karhumäki, Juhani, Klop, Jan Willem, Saarela, Aleksi, 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

17. On Growth and Fluctuation of k-Abelian Complexity

Author

Cassaigne, Julien, Karhumäki, Juhani, Saarela, Aleksi, 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, Beklemishev, Lev D., editor, and Musatov, Daniil V., editor

Published
2015
Full Text
View/download PDF

18. On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages

Author

Karhumäki, Juhani, Okhotin, Alexander, 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, Calude, Cristian S., editor, Freivalds, Rūsiņš, editor, and Kazuo, Iwama, editor

Published
2014
Full Text
View/download PDF

19. On k-Abelian Palindromic Rich and Poor Words

Author

Karhumäki, Juhani, Puzynina, Svetlana, 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, Shur, Arseny M., editor, and Volkov, Mikhail V., editor

Published
2014
Full Text
View/download PDF

20. Variations of the Morse-Hedlund Theorem for k-Abelian Equivalence

Author

Karhumäki, Juhani, Saarela, Aleksi, Zamboni, Luca Q., 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, Shur, Arseny M., editor, and Volkov, Mikhail V., editor

Published
2014
Full Text
View/download PDF

24. 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

25. Equations in the Partial Semigroup of Words with Overlapping Products

Author

Huova, Mari, Karhumäki, Juhani, 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, Bordihn, Henning, editor, Kutrib, Martin, editor, and Truthe, Bianca, editor

Published
2012
Full Text
View/download PDF

26. Weighted Finite Automata: Computing with Different Topologies

Author

Karhumäki, Juhani, Sallinen, Turo, 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, Calude, Cristian S., editor, Kari, Jarkko, editor, Petre, Ion, editor, and Rozenberg, Grzegorz, editor

Published
2011
Full Text
View/download PDF

27. Local Squares, Periodicity and Finite Automata

Author

Huova, Mari, Karhumäki, Juhani, Saarela, Aleksi, Saari, Kalle, 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, Calude, Cristian S., editor, Rozenberg, Grzegorz, editor, and Salomaa, Arto, editor

Published
2011
Full Text
View/download PDF

29. Unique Decipherability in the Monoid of Languages: An Application of Rational Relations

Author

Choffrut, Christian, Karhumäki, Juhani, 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, Frid, Anna, editor, Morozov, Andrey, editor, Rybalchenko, Andrey, editor, and Wagner, Klaus W., editor

Published
2009
Full Text
View/download PDF

30. An Analysis and a Reproof of Hmelevskii’s Theorem : (Extended Abstract)

Author

Karhumäki, Juhani, 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, Ito, Masami, editor, and Toyama, Masafumi, editor

Published
2008
Full Text
View/download PDF

31. On Stateless Multihead Automata: Hierarchies and the Emptiness Problem

Author

Ibarra, Oscar H., Karhumäki, Juhani, Okhotin, Alexander, 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, Laber, Eduardo Sany, editor, Bornstein, Claudson, editor, Nogueira, Loana Tito, editor, and Faria, Luerbio, editor

Published
2008
Full Text
View/download PDF

32. 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

33. Communication of Two Stacks and Rewriting

Author

Karhumäki, Juhani, Kunc, Michal, Okhotin, Alexander, 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, Bugliesi, Michele, editor, Preneel, Bart, editor, Sassone, Vladimiro, editor, and Wegener, Ingo, editor

Published
2006
Full Text
View/download PDF

34. Finite Sets of Words and Computing : (A Survey)

Author

Karhumäki, Juhani, 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, and Margenstern, Maurice, editor

Published
2005
Full Text
View/download PDF

48. On the Centralizer of a Finite Set

Author

Karhumäki, Juhani, Petre, Ion, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Montanari, Ugo, editor, Rolim, José D. P., editor, and Welzl, Emo, editor

Published
2000
Full Text
View/download PDF

49. Measures of Nondeterminism in Finite Automata

Author

Hromkovič, Juraj, Karhumäki, Juhani, Klauck, Hartmut, Schnitger, Georg, Seibert, Sebastian, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Montanari, Ugo, editor, Rolim, José D. P., editor, and Welzl, Emo, editor

Published
2000
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results