Search

Your search keyword '"REIDENBACH, DANIEL"' showing total 182 results
Start Over Author "REIDENBACH, DANIEL"
182 results on '"REIDENBACH, DANIEL"'

1. A Toolkit for Parikh Matrices

Author

Hutchinson, Laura K., Mercaş, Robert, Reidenbach, Daniel, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Caron, Pascal, editor, and Mignot, Ludovic, editor

Published
2022
Full Text
View/download PDF

2. The Billaud Conjecture for , and Beyond

Author

Łopaciuk, Szymon, Reidenbach, Daniel, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Diekert, Volker, editor, and Volkov, Mikhail, editor

Published
2022
Full Text
View/download PDF

5. On Billaud Words and Their Companions

Author

Łopaciuk, Szymon, Reidenbach, Daniel, 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, Lecroq, Thierry, editor, and Puzynina, Svetlana, editor

Published
2021
Full Text
View/download PDF

7. A Polynomial Time Match Test for Large Classes of Extended Regular Expressions

Author

Reidenbach, Daniel and Schmid, Markus L.

Subjects
Computer Science - Formal Languages and Automata Theory
Abstract

In the present paper, we study the match test for extended regular expressions. We approach this NP-complete problem by introducing a novel variant of two-way multihead automata, which reveals that the complexity of the match test is determined by a hidden combinatorial property of extended regular expressions, and it shows that a restriction of the corresponding parameter leads to rich classes with a polynomial time match test. For presentational reasons, we use the concept of pattern languages in order to specify extended regular expressions. While this decision, formally, slightly narrows the scope of our results, an extension of our concepts and results to more general notions of extended regular expressions is straightforward.

Published
2017

10. Reducing the Ambiguity of Parikh Matrices

Author

Dick, Jeffery, Hutchinson, Laura K., Mercaş, Robert, Reidenbach, Daniel, 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, Leporati, Alberto, editor, Martín-Vide, Carlos, editor, Shapira, Dana, editor, and Zandron, Claudio, editor

Published
2020
Full Text
View/download PDF

11. Factorization in Formal Languages

Author

Bell, Paul, Reidenbach, Daniel, and Shallit, Jeffrey

Subjects
Computer Science - Formal Languages and Automata Theory
Abstract

We consider several novel aspects of unique factorization in formal languages. We reprove the familiar fact that the set uf(L) of words having unique factorization into elements of L is regular if L is regular, and from this deduce an quadratic upper and lower bound on the length of the shortest word not in uf(L). We observe that uf(L) need not be context-free if L is context-free. Next, we consider variations on unique factorization. We define a notion of "semi-unique" factorization, where every factorization has the same number of terms, and show that, if L is regular or even finite, the set of words having such a factorization need not be context-free. Finally, we consider additional variations, such as unique factorization "up to permutation" and "up to subset".

Published
2015

13. Unambiguous 1-Uniform Morphisms

Author

Nevisi, Hossein and Reidenbach, Daniel

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

A morphism h is unambiguous with respect to a word w if there is no other morphism g that maps w to the same image as h. In the present paper we study the question of whether, for any given word, there exists an unambiguous 1-uniform morphism, i.e., a morphism that maps every letter in the word to an image of length 1., Comment: In Proceedings WORDS 2011, arXiv:1108.3412

Published
2011
Full Text
View/download PDF

15. Ambiguity of Morphisms in a Free Group

Author

Day, Joel D., Reidenbach, Daniel, 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, Manea, Florin, editor, and Nowotka, Dirk, editor

Published
2015
Full Text
View/download PDF

16. Factorization in Formal Languages

Author

Bell, Paul C., Reidenbach, Daniel, Shallit, Jeffrey, 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, and Potapov, Igor, editor

Published
2015
Full Text
View/download PDF

17. Closure Properties of Pattern Languages

Author

Day, Joel D., Reidenbach, Daniel, Schmid, Markus L., 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

19. Periodicity Forcing Words

Author

Day, Joel D., Reidenbach, Daniel, Schneider, Johannes C., 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, Karhumäki, Juhani, editor, Lepistö, Arto, editor, and Zamboni, Luca, editor

Published
2013
Full Text
View/download PDF

20. On the Dual Post Correspondence Problem

Author

Day, Joel D., Reidenbach, Daniel, Schneider, Johannes C., 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

22. Morphic Primitivity and Alphabet Reductions

Author

Nevisi, Hossein, Reidenbach, Daniel, 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

23. Regular and Context-Free Pattern Languages over Small Alphabets

Author

Reidenbach, Daniel, Schmid, Markus L., 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

24. Automata with Modulo Counters and Nondeterministic Counter Bounds

Author

Reidenbach, Daniel, Schmid, Markus L., 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, Moreira, Nelma, editor, and Reis, Rogério, editor

Published
2012
Full Text
View/download PDF

25. Patterns with Bounded Treewidth

Author

Reidenbach, Daniel, Schmid, Markus L., 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, and Martín-Vide, Carlos, editor

Published
2012
Full Text
View/download PDF

26. Finding Shuffle Words That Represent Optimal Scheduling of Shared Memory Access

Author

Reidenbach, Daniel, Schmid, Markus L., 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, Inenaga, Shunsuke, editor, and Martín-Vide, Carlos, editor

Published
2011
Full Text
View/download PDF

27. A Polynomial Time Match Test for Large Classes of Extended Regular Expressions

Author

Reidenbach, Daniel, Schmid, Markus L., 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, Domaratzki, Michael, editor, and Salomaa, Kai, editor

Published
2011
Full Text
View/download PDF

28. Restricted Ambiguity of Erasing Morphisms

Author

Reidenbach, Daniel, Schneider, Johannes C., 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, Gao, Yuan, editor, Lu, Hanlin, editor, Seki, Shinnosuke, editor, and Yu, Sheng, editor

Published
2010
Full Text
View/download PDF

30. Existence and Nonexistence of Descriptive Patterns

Author

Freydenberger, Dominik D., Reidenbach, Daniel, 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, Diekert, Volker, editor, and Nowotka, Dirk, editor

Published
2009
Full Text
View/download PDF

31. Bad News on Decision Problems for Patterns

Author

Freydenberger, Dominik D., Reidenbach, Daniel, 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

32. The Unambiguity of Segmented Morphisms

Author

Freydenberger, Dominik D., Reidenbach, Daniel, 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

33. Unambiguous Morphic Images of Strings

Author

Freydenberger, Dominik D., Reidenbach, Daniel, Schneider, Johannes C., 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, De Felice, Clelia, editor, and Restivo, Antonio, editor

Published
2005
Full Text
View/download PDF

34. On the Equivalence Problem for E-Pattern Languages Over Small Alphabets

Author

Reidenbach, Daniel, 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, Calude, Cristian S., editor, Calude, Elena, editor, and Dinneen, Michael J., editor

Published
2005
Full Text
View/download PDF

35. On the Learnability of E-pattern Languages over Small Alphabets

Author

Reidenbach, Daniel, 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, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Shawe-Taylor, John, editor, and Singer, Yoram, editor

Published
2004
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results