Latest documents http://publikationen.stub.uni-frankfurt.de/index/index/ Thu, 15 Sep 2011 14:16:18 +0200 Thu, 15 Sep 2011 14:16:18 +0200 http://publikationen.stub.uni-frankfurt.de/frontdoor/index/index/docId/22713 The paper describes a simple and fast randomized test for equality of grammar-compressed strings. The thorough running time analysis is done by applying a logarithmic cost measure. Keywords: randomized algorithms, straight line programs, grammar-based compression Manfred Schmidt-Schauß; Georg Schnitger workingpaper http://publikationen.stub.uni-frankfurt.de/frontdoor/index/index/docId/22713 Thu, 15 Sep 2011 14:16:18 +0200 http://publikationen.stub.uni-frankfurt.de/frontdoor/index/index/docId/7580 The ambiguity of a nondeterministic finite automaton (NFA) N for input size n is the maximal number of accepting computations of N for an input of size n. For all k, r 2 N we construct languages Lr,k which can be recognized by NFA's with size k poly(r) and ambiguity O(nk), but Lr,k has only NFA's with exponential size, if ambiguity o(nk) is required. In particular, a hierarchy for polynomial ambiguity is obtained, solving a long standing open problem (Ravikumar and Ibarra, 1989, Leung, 1998). Juraj Hromkovič; Georg Schnitger conferenceobject http://publikationen.stub.uni-frankfurt.de/frontdoor/index/index/docId/7580 Tue, 09 Mar 2010 17:23:42 +0100