On 2PFA's and the Hadamard quotient of formal power series.
Random generation for finitely ambiguous context-free languages
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.
Random Generation for Finitely Ambiguous Context-free Languages
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.
Regularity of languages defined by formal series with isolated cut point
Let = { ∈ | () } be the language recognized by a formal series : → ℝ with isolated cut point . We provide new conditions that guarantee the regularity of the language in the case that is rational or is a Hadamard quotient of rational series. Moreover the decidability property of such conditions is investigated.
Regularity of languages defined by formal series with isolated cut point
Let = { ∈ | () } be the language recognized by a formal series : → ℝ with isolated cut point . We provide new conditions that guarantee the regularity of the language in the case that is rational or is a Hadamard quotient of rational series. Moreover the decidability property of such conditions is investigated.
Regularity of languages defined by formal series with isolated cut point
Let = { ∈ | () } be the language recognized by a formal series : → ℝ with isolated cut point . We provide new conditions that guarantee the regularity of the language in the case that is rational or is a Hadamard quotient of rational series. Moreover the decidability property of such conditions is investigated.
Page 1