Displaying similar documents to “Random generation for finitely ambiguous context-free languages”

Complexity results for prefix grammars

Markus Lohrey, Holger Petersen (2005)

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

Similarity:

Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.

String distances and intrusion detection: Bridging the gap between formal languages and computer security

Danilo Bruschi, Giovanni Pighizzini (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper we analyze some intrusion detection strategies proposed in the literature and we show that they represent the various facets of a well known formal languages problem: computing the distance between a string and a language . In particular, the main differences among the various approaches adopted for building intrusion detection systems can be reduced to the characteristics of the language and to the notion of distance adopted. As a further contribution we will also show...