Lower bounds on the complexity of real-time branching programs
Klaus Kriegel, Stephan Waack · RAIRO - Theoretical Informatics and Applications · 1988
A (2 m)" /24 lower bound is given for the real-time décision graph complexity of the Dyck language D *.Furthermore, a 2 n/4 *Jower bound for the real-time branching program complexity of an encoding of the Dyck language DJ is proved.Previously known similar lower bounds are 2 e ", c« 10" 13 , for one-time-only branching programs (a less powerful model), and 2 nt V 5) for realtime branching programs.Résumé.-Dans cet article, nous montrons que le nombre de noeuds d'un arbre de décision en temps réel pour le langage de Dyck D* est borné inférieurement par (2m)" /24 .On donne également une borne inférieure en 2" /48 pour la complexité des programmes temps réel pour un codage du langage de Dyck D*-Les bornes précédemment connues étaient en 2 e " avec c«10~1 3 pour les programmes à un seul branchement (un modèle moins puissant) et en 2 n ( V n) pour les programmes à branchements temps réel.