Currently displaying 1 – 6 of 6

Showing per page

Order by Relevance | Title | Year of publication

Random generation for finitely ambiguous context-free languages

Alberto BertoniMassimiliano GoldwurmMassimo Santini — 2001

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We prove that a word of length n from a finitely ambiguous context-free language can be generated at random under uniform distribution in O ( n 2 log n ) 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 1 -NAuxPDA with polynomially bounded ambiguity.

Random Generation for Finitely Ambiguous Context-free Languages

Alberto BertoniMassimiliano GoldwurmMassimo Santini — 2010

RAIRO - Theoretical Informatics and Applications

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

Alberto BertoniMaria Paola BianchiFlavi D’Alessandro — 2012

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

Alberto BertoniMaria Paola BianchiFlavi D’Alessandro — 2012

RAIRO - Theoretical Informatics and Applications

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

Alberto BertoniMaria Paola BianchiFlavi D’Alessandro — 2012

RAIRO - Theoretical Informatics and Applications

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

Download Results (CSV)