We prove that a word of length from a finitely ambiguous context-free language can be generated at random under uniform distribution in time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time -NAuxPDA with polynomially bounded ambiguity.
We prove that a word of length from a finitely ambiguous context-free language can be generated at random under uniform distribution in ( log ) time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time -NAuxPDA with polynomially bounded ambiguity.
PageRank is a ranking method that assigns scores to web pages using the limit distribution of a random walk on the web graph. A of graphs is a morphism that is a local isomorphism of in-neighbourhoods, much in the same way a covering projection is a local isomorphism of neighbourhoods. We show that a deep connection relates fibrations and , a particular kind of Markov chains that include the PageRank one as a special case. This fact provides constraints on the values that PageRank can assume....
Page 1