Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data.

Klaus Wich

dblp:53/301 · DBLP profile ↗
← Back
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

TopicWeightPapersLastEvidence papers
Information theory › signal processing › time-frequency analysis
ambiguity function
0.012002
Universal Inherence of Cycle-Free Context-Free Ambiguity Functions · ICALP 2002
Automata and formal languages
context-free languages
0.012002
Universal Inherence of Cycle-Free Context-Free Ambiguity Functions · ICALP 2002
YearPublicationVenuePosition
2005 Sublogarithmic ambiguity
Klaus Wich
Theor. Comput. Sci.1
2004 Sublogarithmic Ambiguity
Klaus Wich
MFCS1
2002 Universal Inherence of Cycle-Free Context-Free Ambiguity Functions
Klaus Wich
ICALP1
2001 Characterization of Context-Free Languages with Polynomially Bounded Ambiguity
Klaus Wich
MFCS1
2000 Sublinear Ambiguity
Klaus Wich
MFCS1
1999 Exponential ambiguity of context-free grammars
abstract
A 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 Theory1