Holger Petersen

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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2019
Some Remarks on Real-Time Turing Machines.
CoRR, 2019

LIKE Patterns and Complexity.
Proceedings of the Computing and Combinatorics - 25th International Conference, 2019

2017
Busy Beaver Scores and Alphabet Size.
Proceedings of the Fundamentals of Computation Theory - 21st International Symposium, 2017

2016
A Note on Nested String Replacements.
CoRR, 2016

Simpler, faster and shorter labels for distances in graphs.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015
Counting Ones Without Broadword Operations.
CoRR, 2015

The Complexity of Some Combinatorial Puzzles.
CoRR, 2015

An NL-Complete Puzzle.
CoRR, 2015

A Non-Oblivious Reduction of Counting Ones to Multiplication.
CoRR, 2015

Efficient Computation by Three Counter Machines.
CoRR, 2015

2014
On Practical Regular Expressions.
CoRR, 2014

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

A Note on Pushdown Automata Systems.
Proceedings of the Descriptional Complexity of Formal Systems, 2014

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

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

The Power of Centralized PC Systems of Pushdown Automata.
Proceedings of the Descriptional Complexity of Formal Systems, 2013

2012
A Note on Kolmogorov-Uspensky Machines
CoRR, 2012

Bounded Counter Languages.
Proceedings of the Descriptional Complexity of Formal Systems, 2012

2011
Simulations by Time-Bounded Counter Machines.
Int. J. Found. Comput. Sci., 2011

A SWAR Approach to Counting Ones
CoRR, 2011

Marriage Broker.
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.
Theor. Comput. Sci., 2009

Range mode and range median queries in constant time and sub-quadratic space.
Inf. Process. Lett., 2009

2008
Partnerschaftsvermittlung.
Proceedings of the Taschenbuch der Algorithmen, 2008

Improved Bounds for Range Mode and Range Median Queries.
Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

Element Distinctness and Sorting on One-Tape Off-Line Turing Machines.
Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

Sorting and Element Distinctness on One-Way Turing Machines.
Proceedings of the Language and Automata Theory and Applications, 2008

2007
String matching with simple devices.
Inf. Process. Lett., 2007

2006
Computable Lower Bounds for Busy Beaver Turing Machines.
Proceedings of the Recent Advances in Formal Languages and Applications, 2006

Efficient Simulations by Queue Machines.
SIAM J. Comput., 2006

Backing up in singly linked lists.
J. ACM, 2006

2005
Regular frequency computations.
Theor. Comput. Sci., 2005

Complexity results for prefix grammars.
RAIRO Theor. Informatics Appl., 2005

2004
A Note On Rebound Turing Machines.
Int. J. Found. Comput. Sci., 2004

2003
Information Security Management - Vom Prozess zur Umsetzung.
Datenschutz und Datensicherheit, 2003

Konzepte zum Root-CA Zertifikatswechsel.
Datenschutz und Datensicherheit, 2003

Element distinctness on one-tape Turing machines: a complete solution.
Acta Informatica, 2003

Complexity Results for Prefix Grammars.
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.
Theory Comput. Syst., 2002

Bounds for the Element Distinctness Problem on one-tape Turing machines.
Inf. Process. Lett., 2002

The Membership Problem for Regular Expressions with Intersection Is Complete in LOGCFL.
Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

2001
Stacks versus Deques.
Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

2000
Prefix Rewriting and Descriptional Complexity.
J. Autom. Lang. Comb., 2000

Separation Results for Rebound Automata.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

1999
Cryptographic Copyright Protection for Digital Images Based on Watermarking Techniques.
Theor. Comput. Sci., 1999

Separating Words with Small Grammars.
J. Autom. Lang. Comb., 1999

Privilege Management Infrastructure - PMI.
Datenschutz und Datensicherheit, 1999

Fooling Rebound Automata.
Proceedings of the Mathematical Foundations of Computer Science 1999, 1999

1998
The Head Hierarchy for Oblivious Finite Automata with Polynomial Advice Collapses.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

Secure Copyright Protection Techniques for Digital Images.
Proceedings of the Information Hiding, 1998

CONS-Free Programs with Tree Input (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

1997
How to Convert any Digital Signature Scheme into a Group Signature Scheme.
Proceedings of the Security Protocols, 1997

Homomorphic Images os Sentential Forms and Terminating Grammars (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

The Equivalence of Pebbles and Sensing Heads for Finite Automata.
Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

1996
On the Language of Primitive Words.
Theor. Comput. Sci., 1996

The Computation of Partial Recursive Word-Functions Without Read Instructions.
Math. Log. Q., 1996

A Note on the Commutative Closure of Star-Free Languages.
Inf. Process. Lett., 1996

Entscheidbarkeitsfragen und Hierarchieresultate für Mehrkopfautomaten.
PhD thesis, 1996

1995
A Remark on a Paper by Armando B. Matos.
Theor. Comput. Sci., 1995

On Space Functions Fully Constructed by Two-Dimensional Turing Machines.
Inf. Process. Lett., 1995

Automata with Sensing Heads.
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

Alternation in Simple Devices.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Some Results Concerning Two-Dimensional Turing Machines and Finite Automata.
Proceedings of the Fundamentals of Computation Theory, 10th International Symposium, 1995

1994
Cancellation in Context-Free Languages: Enrichment by Reduction.
Theor. Comput. Sci., 1994

Two-way one-counter automata accepting bounded languages.
SIGACT News, 1994

On the Determinacy Problem for Two-Way Pushdown Automata.
Inf. Process. Lett., 1994

Refined Simulation of Multihead Automata.
Inf. Process. Lett., 1994

Notes on Looping Deterministic Two-Way Pushdown Automata.
Inf. Process. Lett., 1994

The Ambiguity of Primitive Words.
Proceedings of the STACS 94, 1994

1987
Dyck<sub>1</sub>-Reductions of Context-free Languages.
Proceedings of the Fundamentals of Computation Theory, 1987


  Loading...