Holger Petersen
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Holger Petersen has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
Amir M. Ben-Amram
The Academic College of Tel-Aviv-Yaffo, Tel-Aviv, Israel
1 shared publication- Amir M. Ben-Amram
School of Computing Dublin City University Ireland
1 shared publication - Amir M. Ben-Amram
Tel-Aviv Academic College, 4 Antokolski Street, 64044 Tel-Aviv, Israel.
1 shared publication - Anca Muscholl
Institut für Informatik, Universität Stuttgart, Breitwiesenstraβe 20-22, D-70565 Stuttgart, Germany
1 shared publication - John Michael Robson
LaBRI Université Bordeaux 1 351 Cours de la Libération 33405 Talence France
1 shared publication - Markus Lohrey
Universität Leipzig
1 shared publication
Latest Publications
- 31 December 2007
- Published by Elsevier in Information Processing Letters
- Vol. 105 (1) , 32-34
String matching with simple devices
- 31 December 2007
- Published by Elsevier in Information Processing Letters
- Vol. 105 (1) , 32-34
String matching with simple devices
- Open Access
- 15 April 2005
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 39 (2) , 391-401
Complexity results for prefix grammars
Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.
- 15 April 2005
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 39 (2) , 391-401
Open AccessComplexity results for prefix grammars
Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.
- 1 October 2003
- Published by Springer Nature in Acta Informatica
- Vol. 40 (2) , 81-94
Element distinctness on one-tape Turing machines: a complete solution
- 1 October 2003
- Published by Springer Nature in Acta Informatica
- Vol. 40 (2) , 81-94
Element distinctness on one-tape Turing machines: a complete solution
- 1 January 2002
- Published by Springer Nature in Theory of Computing Systems
- Vol. 35 (1) , 1-11
Improved Bounds for Functions Related to Busy Beavers
- 1 January 2002
- Published by Springer Nature in Theory of Computing Systems
- Vol. 35 (1) , 1-11
Improved Bounds for Functions Related to Busy Beavers
- 1 January 1998
- Published by Springer Nature
- p. 884-895
Efficient simulations by queue machines
- 1 January 1998
- Published by Springer Nature
- p. 296-304
The head hierarchy for oblivious finite automata with polynomial advice collapses
- 1 January 1998
- Published by Springer Nature
- p. 296-304
The head hierarchy for oblivious finite automata with polynomial advice collapses
- 1 January 1997
- Published by Springer Nature
- p. 400-410
The equivalence of pebbles and sensing heads for finite automata
- 1 January 1997
- Published by Springer Nature
- p. 400-410
The equivalence of pebbles and sensing heads for finite automata
- 1 January 1997
- Published by Springer Nature
- p. 448-457
Homomorphic images of sentential forms and terminating grammars (extended abstract)
- 1 January 1997
- Published by Springer Nature
- p. 448-457
Homomorphic images of sentential forms and terminating grammars (extended abstract)
- 29 January 1996
- Published by Elsevier in Information Processing Letters
- Vol. 57 (2) , 71-74
A note on the commutative closure of star-free languages
- 29 January 1996
- Published by Elsevier in Information Processing Letters
- Vol. 57 (2) , 71-74
A note on the commutative closure of star-free languages