EDBT 2026 Demo / reviewers in the wild / expert
Klaus Wich
dblp:53/301
· DBLP profile ↗
6ranked-venue papers
6as first author
0since 2021 · last 2005
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 6 · 6 first-author
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
1 paper |
Automata and formal languages · 50% Information theory · 50% |
Topics — the 2 heaviest of 2, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Information theory › signal processing › time-frequency analysis
ambiguity function |
0.0 | 1 | 2002 | Universal Inherence of Cycle-Free Context-Free Ambiguity Functions · ICALP 2002 |
Automata and formal languages
context-free languages |
0.0 | 1 | 2002 | Universal Inherence of Cycle-Free Context-Free Ambiguity Functions · ICALP 2002 |
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2005 | Sublogarithmic ambiguity
Klaus Wich |
Theor. Comput. Sci. | 1 |
| 2004 | Sublogarithmic Ambiguity
Klaus Wich |
MFCS | 1 |
| 2002 | Universal Inherence of Cycle-Free Context-Free Ambiguity Functions
Klaus Wich |
ICALP | 1 |
| 2001 | Characterization of Context-Free Languages with Polynomially Bounded Ambiguity
Klaus Wich |
MFCS | 1 |
| 2000 | Sublinear Ambiguity
Klaus Wich |
MFCS | 1 |
| 1999 | Exponential ambiguity of context-free grammarsabstractA context-free grammar G is ambiguous if and only if there is a word that can be generated by G with at least two different derivation trees. Ambiguous grammars are often distinguished by their degree of ambiguity, which is the maximal number of derivation trees for the words generated by them. If there is no such upper bound G is said to be ambiguous of infinite degree. Here as a new tool for examining the ambiguity of cyclefree context-free grammars the ambiguity function is introduced. This function maps the natural number n to the maximal number of derivation trees which a word of length at most n may have. This provides the possibility to distinguish infinitely ambiguous context-free grammars by the growth-rate of their ambiguity functions. We present a necessary and sufficient, but in general undecidable, criterion for exponential ambiguity. In fact violation of this criterion leads to a polynomial upper bound for the ambiguity, which can be effectively constructed from the grammar. Hence for cycle-free context-free grammars the ambiguity function is either an element of 2 Θ(n) or of O(n d) for some d ∈ N0 which can be effectively constructed from G. 1 Klaus Wich |
Developments in Language Theory | 1 |