Holger Petersen

Affiliations:

University of Stuttgart, Germany

According to our database¹, Holger Petersen authored at least 70 papers between 1987 and 2019.

Collaborative distances:

Dijkstra number² of four.
Erdős number³ of three.

Timeline

Legend:

Book

In proceedings

Article

PhD thesis

Dataset

Other

Links

On csauthors.net:

Bibliography

2019

Some Remarks on Real-Time Turing Machines.

[BibT_eX]

[DOI]

Holger Petersen

CoRR, 2019

LIKE Patterns and Complexity.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Computing and Combinatorics - 25th International Conference, 2019

2017

Busy Beaver Scores and Alphabet Size.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Fundamentals of Computation Theory - 21st International Symposium, 2017

2016

A Note on Nested String Replacements.

[BibT_eX]

[DOI]

Holger Petersen

CoRR, 2016

Simpler, faster and shorter labels for distances in graphs.

[BibT_eX]

[DOI]

Stephen Alstrup

Cyril Gavoille

Esben Bistrup Halvorsen

Holger Petersen

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

Counting Ones Without Broadword Operations.

[BibT_eX]

[DOI]

Holger Petersen

CoRR, 2015

The Complexity of Some Combinatorial Puzzles.

[BibT_eX]

[DOI]

Holger Petersen

CoRR, 2015

An NL-Complete Puzzle.

[BibT_eX]

[DOI]

Holger Petersen

CoRR, 2015

A Non-Oblivious Reduction of Counting Ones to Multiplication.

[BibT_eX]

[DOI]

Holger Petersen

CoRR, 2015

Efficient Computation by Three Counter Machines.

[BibT_eX]

[DOI]

Holger Petersen

CoRR, 2015

2014

On Practical Regular Expressions.

[BibT_eX]

[DOI]

Holger Petersen

CoRR, 2014

Professionelles Testmanagement in Datenreinigungsprozessen.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the 44. Jahrestagung der Gesellschaft für Informatik, Big Data, 2014

A Note on Pushdown Automata Systems.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Descriptional Complexity of Formal Systems, 2014

2013

Some Remarks on Lower Bounds for Queues Machines (Preliminary Report).

[BibT_eX]

[DOI]

Holger Petersen

CoRR, 2013

A Note on Asynchronous PC Systems of Pushdown Automata (Preliminary Report).

[BibT_eX]

[DOI]

Holger Petersen

CoRR, 2013

The Power of Centralized PC Systems of Pushdown Automata.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Descriptional Complexity of Formal Systems, 2013

2012

A Note on Kolmogorov-Uspensky Machines

[BibT_eX]

[DOI]

Holger Petersen

CoRR, 2012

Bounded Counter Languages.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Descriptional Complexity of Formal Systems, 2012

2011

Simulations by Time-Bounded Counter Machines.

[BibT_eX]

[DOI]

Holger Petersen

Int. J. Found. Comput. Sci., 2011

A SWAR Approach to Counting Ones

[BibT_eX]

[DOI]

Holger Petersen

CoRR, 2011

Marriage Broker.

[BibT_eX]

[DOI]

Volker Claus

Volker Diekert

Holger Petersen

Proceedings of the Algorithms Unplugged, 2011

2009

On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's.

[BibT_eX]

[DOI]

Juraj Hromkovic

Holger Petersen

Georg Schnitger

Theor. Comput. Sci., 2009

Range mode and range median queries in constant time and sub-quadratic space.

[BibT_eX]

[DOI]

Holger Petersen

Szymon Grabowski

Inf. Process. Lett., 2009

2008

Partnerschaftsvermittlung.

[BibT_eX]

[DOI]

Volker Claus

Volker Diekert

Holger Petersen

Proceedings of the Taschenbuch der Algorithmen, 2008

Improved Bounds for Range Mode and Range Median Queries.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

Element Distinctness and Sorting on One-Tape Off-Line Turing Machines.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

Sorting and Element Distinctness on One-Way Turing Machines.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Language and Automata Theory and Applications, 2008

2007

String matching with simple devices.

[BibT_eX]

[DOI]

Holger Petersen

Inf. Process. Lett., 2007

2006

Computable Lower Bounds for Busy Beaver Turing Machines.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Recent Advances in Formal Languages and Applications, 2006

Efficient Simulations by Queue Machines.

[BibT_eX]

[DOI]

Holger Petersen

John Michael Robson

SIAM J. Comput., 2006

Backing up in singly linked lists.

[BibT_eX]

[DOI]

Amir M. Ben-Amram

Holger Petersen

J. ACM, 2006

2005

Regular frequency computations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Complexity results for prefix grammars.

[BibT_eX]

[DOI]

Markus Lohrey

Holger Petersen

RAIRO Theor. Informatics Appl., 2005

2004

A Note On Rebound Turing Machines.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2004

2003

Information Security Management - Vom Prozess zur Umsetzung.

[BibT_eX]

Dörte Neundorf

Holger Petersen

Datenschutz und Datensicherheit, 2003

Konzepte zum Root-CA Zertifikatswechsel.

[BibT_eX]

Ingmar Camphausen

Holger Petersen

Claus Stark

Datenschutz und Datensicherheit, 2003

Element distinctness on one-tape Turing machines: a complete solution.

[BibT_eX]

[DOI]

Amir M. Ben-Amram

Omer Berkman

Holger Petersen

Acta Informatica, 2003

Complexity Results for Prefix Grammars.

[BibT_eX]

Holger Petersen

Proceedings of the 5th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2003, Budapest, Hungary, July 12, 2003

2002

Improved Bounds for Functions Related to Busy Beavers.

[BibT_eX]

[DOI]

Amir M. Ben-Amram

Holger Petersen

Theory Comput. Syst., 2002

Bounds for the Element Distinctness Problem on one-tape Turing machines.

[BibT_eX]

[DOI]

Holger Petersen

Inf. Process. Lett., 2002

The Membership Problem for Regular Expressions with Intersection Is Complete in LOGCFL.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

2001

Stacks versus Deques.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

2000

Prefix Rewriting and Descriptional Complexity.

[BibT_eX]

[DOI]

Holger Petersen

J. Autom. Lang. Comb., 2000

Separation Results for Rebound Automata.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

1999

Cryptographic Copyright Protection for Digital Images Based on Watermarking Techniques.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1999

Separating Words with Small Grammars.

[BibT_eX]

[DOI]

J. Autom. Lang. Comb., 1999

Privilege Management Infrastructure - PMI.

[BibT_eX]

Holger Petersen

Datenschutz und Datensicherheit, 1999

Fooling Rebound Automata.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Mathematical Foundations of Computer Science 1999, 1999

1998

The Head Hierarchy for Oblivious Finite Automata with Polynomial Advice Collapses.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

Secure Copyright Protection Techniques for Digital Images.

[BibT_eX]

[DOI]

Proceedings of the Information Hiding, 1998

CONS-Free Programs with Tree Input (Extended Abstract).

[BibT_eX]

[DOI]

Amir M. Ben-Amram

Holger Petersen

Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

1997

How to Convert any Digital Signature Scheme into a Group Signature Scheme.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Security Protocols, 1997

Homomorphic Images os Sentential Forms and Terminating Grammars (Extended Abstract).

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

The Equivalence of Pebbles and Sensing Heads for Finite Automata.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

1996

On the Language of Primitive Words.

[BibT_eX]

[DOI]

Holger Petersen

Theor. Comput. Sci., 1996

The Computation of Partial Recursive Word-Functions Without Read Instructions.

[BibT_eX]

[DOI]

Holger Petersen

Math. Log. Q., 1996

A Note on the Commutative Closure of Star-Free Languages.

[BibT_eX]

[DOI]

Anca Muscholl

Holger Petersen

Inf. Process. Lett., 1996

Entscheidbarkeitsfragen und Hierarchieresultate für Mehrkopfautomaten.

[BibT_eX]

[DOI]

Holger Petersen

PhD thesis, 1996

1995

A Remark on a Paper by Armando B. Matos.

[BibT_eX]

[DOI]

Holger Petersen

Theor. Comput. Sci., 1995

On Space Functions Fully Constructed by Two-Dimensional Turing Machines.

[BibT_eX]

[DOI]

Holger Petersen

Inf. Process. Lett., 1995

Automata with Sensing Heads.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

Alternation in Simple Devices.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Some Results Concerning Two-Dimensional Turing Machines and Finite Automata.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the Fundamentals of Computation Theory, 10th International Symposium, 1995

1994

Cancellation in Context-Free Languages: Enrichment by Reduction.

[BibT_eX]

[DOI]

Matthias Jantzen

Holger Petersen

Theor. Comput. Sci., 1994

Two-way one-counter automata accepting bounded languages.

[BibT_eX]

[DOI]

Holger Petersen

SIGACT News, 1994

On the Determinacy Problem for Two-Way Pushdown Automata.

[BibT_eX]

[DOI]

Holger Petersen

Inf. Process. Lett., 1994

Refined Simulation of Multihead Automata.

[BibT_eX]

[DOI]

Holger Petersen

Inf. Process. Lett., 1994

Notes on Looping Deterministic Two-Way Pushdown Automata.

[BibT_eX]

[DOI]

M. Ladermann

Holger Petersen

Inf. Process. Lett., 1994

The Ambiguity of Primitive Words.

[BibT_eX]

[DOI]

Holger Petersen

Proceedings of the STACS 94, 1994

1987

Dyck<sub>1</sub>-Reductions of Context-free Languages.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 1987

Holger Petersen

Timeline

Legend:

Links

On csauthors.net:

Bibliography

Loading...