Combinatorial systems defined over one- and two-letter alphabets.
Page 1
Displaying 1 – 5 of 5
Complexity results for prefix grammars
Markus Lohrey, Holger Petersen (2005)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
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.
Complexity results for prefix grammars
Markus Lohrey, Holger Petersen (2010)
RAIRO - Theoretical Informatics and Applications
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.
Congruences parfaites et quasi-parfaites
Maurice Nivat (1971/1972)
Séminaire Dubreil. Algèbre et théorie des nombres
Conjugacy in monoids.
F. Otto (1984)
Semigroup forum
Currently displaying 1 – 5 of 5
Page 1