Search

Your search keyword '"Krieger, Dalia"' showing total 26 results
Start Over Author "Krieger, Dalia"
26 results on '"Krieger, Dalia"'

1. An autonomous debating system

Author

Slonim, Noam, Bilu, Yonatan, Alzate, Carlos, Bar-Haim, Roy, Bogin, Ben, Bonin, Francesca, Choshen, Leshem, Cohen-Karlik, Edo, Dankin, Lena, Edelstein, Lilach, Ein-Dor, Liat, Friedman-Melamed, Roni, Gavron, Assaf, Gera, Ariel, Gleize, Martin, Gretz, Shai, Gutfreund, Dan, Halfon, Alon, Hershcovich, Daniel, Hoory, Ron, Hou, Yufang, Hummel, Shay, Jacovi, Michal, Jochim, Charles, Kantor, Yoav, Katz, Yoav, Konopnicki, David, Kons, Zvi, Kotlerman, Lili, Krieger, Dalia, Lahav, Dan, Lavee, Tamar, Levy, Ran, Liberman, Naftali, Mass, Yosi, Menczel, Amir, Mirkin, Shachar, Moshkowich, Guy, Ofek-Koifman, Shila, Orbach, Matan, Rabinovich, Ella, Rinott, Ruty, Shechtman, Slava, Sheinwald, Dafna, Shnarch, Eyal, Shnayderman, Ilya, Soffer, Aya, Spector, Artem, Sznajder, Benjamin, Toledo, Assaf, Toledo-Ronen, Orith, Venezian, Elad, and Aharonov, Ranit

Published
2021
Full Text
View/download PDF

2. Morphic and Automatic Words: Maximal Blocks and Diophantine Approximation

Author

Bugeaud, Yann, Krieger, Dalia, and Shallit, Jeffrey

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

Let $\mb w$ be a morphic word over a finite alphabet $\Sigma$, and let $\Delta$ be a nonempty subset of $\Sigma$. We study the behavior of maximal blocks consisting only of letters from $\Delta$ in $\mb w$, and prove the following: let $(i_k,j_k)$ denote the starting and ending positions, respectively, of the $k$'th maximal $\Delta$-block in $\mb w$. Then $\limsup_{k\to\infty} (j_k/i_k)$ is algebraic if $\mb w$ is morphic, and rational if $\mb w$ is automatic. As a result, we show that the same conclusion holds if $(i_k,j_k)$ are the starting and ending positions of the $k$'th maximal zero block, and, more generally, of the $k$'th maximal $x$-block, where $x$ is an arbitrary word. This enables us to draw conclusions about the irrationality exponent of automatic and morphic numbers. In particular, we show that the irrationality exponent of automatic (resp., morphic) numbers belonging to a certain class that we define is rational (resp., algebraic)., Comment: 16 pages, 1 figure

Published
2008

3. The critical exponent of the Arshon words

Author

Krieger, Dalia

Subjects
Mathematics - Combinatorics, 68R15
Abstract

Generalizing the results of Thue (for n = 2) and of Klepinin and Sukhanov (for n = 3), we prove that for all n greater than or equal to 2, the critical exponent of the Arshon word of order $n$ is given by (3n-2)/(2n-2), and this exponent is attained at position 1., Comment: 11 pages

Published
2008

4. Finding the growth rate of a regular language in polynomial time

Author

Krieger, Dalia, Rampersad, Narad, and Shallit, Jeffrey

Subjects
Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms, F.4.3
Abstract

We give an O(n^3+n^2 t) time algorithm to determine whether an NFA with n states and t transitions accepts a language of polynomial or exponential growth. We also show that given a DFA accepting a language of polynomial growth, we can determine the order of polynomial growth in quadratic time.

Published
2007

5. Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time

Author

Gawrychowski, Paweł, Krieger, Dalia, Rampersad, Narad, Shallit, Jeffrey, 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

6. Avoiding Approximate Squares

Author

Krieger, Dalia, Ochem, Pascal, Rampersad, Narad, Shallit, Jeffrey, 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, Harju, Tero, editor, Karhumäki, Juhani, editor, and Lepistö, Arto, editor

Published
2007
Full Text
View/download PDF

7. On Critical Exponents in Fixed Points of Non-erasing Morphisms

Author

Krieger, Dalia, 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, Ibarra, Oscar H., editor, and Dang, Zhe, editor

Published
2006
Full Text
View/download PDF

8. On Critical Exponents in Fixed Points of Binary k-Uniform Morphisms

Author

Krieger, Dalia, 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, Dough, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Durand, Bruno, editor, and Thomas, Wolfgang, editor

Published
2006
Full Text
View/download PDF

22. Avoiding Approximate Squares.

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Pandu Rangan, C., Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Harju, Tero, Karhumäki, Juhani, Lepistö, Arto, Krieger, Dalia, and Ochem, Pascal

Abstract

As is well-known, Axel Thue constructed an infinite word over a 3-letter alphabet that contains no squares, that is, no nonempty subwords of the form xx. In this paper we consider a variation on this problem, where we try to avoid approximate squares, that is, subwords of the form xx′ where x = x′ and x and x′ are "nearly" identical. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

23. On Critical Exponents in Fixed Points of Non-erasing Morphisms.

Author

Ibarra, Oscar, Zhe Dang, and Krieger, Dalia

Abstract

Let Σ be an alphabet of size t, let f:Σ*→Σ* be a non-erasing morphism, let w be an infinite fixed point of f, and let E(w) be the critical exponent of w. We prove that if E(w) is finite, then for a uniform f it is rational, and for a non-uniform f it lies in the field extension ${{\mathbb Q}[{\lambda_1},\ldots,{\lambda_\ell}]}$, where λ1,...,λℓ are the eigenvalues of the incidence matrix of f. In particular, E(w) is algebraic of degree at most t. Under certain conditions, our proof implies an algorithm for computing E(w). MSC: 68R15 Keywords: Critical exponent; Circular D0L languages. [ABSTRACT FROM AUTHOR]

Published
2006
Full Text
View/download PDF

24. On Critical Exponents in Fixed Points of Binary k-Uniform Morphisms.

Author

Durand, Bruno, Thomas, Wolfgang, and Krieger, Dalia

Abstract

Let be an infinite fixed point of a binary k-uniform morphism f, and let be the critical exponent of . We give necessary and sufficient conditions for to be bounded, and an explicit formula to compute it when it is. In particular, we show that is always rational. We also sketch an extension of our method to non-uniform morphisms over general alphabets. MSC: 68R15. Keywords: Critical exponent; Binary k-uniform morphism. [ABSTRACT FROM AUTHOR]

Published
2006
Full Text
View/download PDF

25. ON CRITICAL EXPONENTS IN FIXED POINTS OF κ-UNIFORM BINARY MORPHISMS.

Author

KRIEGER, DALIA

Subjects
EXPONENTS, NUMERICAL solutions to equations, MORPHISMS (Mathematics), ALGEBRA, CATEGORIES (Mathematics), SET theory, MATHEMATICS, ALPHABET, ARITHMETIC
Abstract

Let w be an infinite fixed point of a binary k-uniform morphism f, and let E(w) be the critical exponent of w. We give necessary and sufficient conditions for E(w) to be bounded, and an explicit formula to compute it when it is. In particular, we show that E(w) is always rational. We also sketch an extension of our method to non-uniform morphisms over general alphabets. [ABSTRACT FROM AUTHOR]

Published
2009
Full Text
View/download PDF

26. On Critical exponents in fixed points of k-uniform binary morphisms

Author

Krieger, Dalia

Abstract

Let wbe an infinite fixed point of a binary k-uniform morphism f, and let Ewbe the critical exponent of w. We give necessary and sufficient conditions for Ewto be bounded, and an explicit formula to compute it when it is. In particular, we show that Ewis always rational. We also sketch an extension of our method to non-uniform morphisms over general alphabets.

Published
2009
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results