Index: /stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/GrammarUtils.cs
===================================================================
--- /stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/GrammarUtils.cs	(revision 14958)
+++ /stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/GrammarUtils.cs	(revision 14958)
@@ -0,0 +1,166 @@
+﻿#region License Information
+
+/* HeuristicLab
+ * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#endregion
+
+using System;
+using System.Collections.Generic;
+using System.Linq;
+namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
+  public static class GrammarUtils {
+    private static IEnumerable<ISymbol> GetTopmostSymbols(this ISymbolicExpressionGrammarBase grammar) {
+      // build parents list so we can find out the topmost symbol(s)
+      var parents = new Dictionary<ISymbol, List<ISymbol>>();
+      foreach (var symbol in grammar.Symbols.Where(x => grammar.GetMinimumSubtreeCount(x) > 0)) {
+        var minSubtreeCount = grammar.GetMinimumSubtreeCount(symbol);
+        for (int argIndex = 0; argIndex < minSubtreeCount; ++argIndex) {
+          foreach (var childSymbol in grammar.GetAllowedActiveSymbols(symbol, argIndex)) {
+            if (!parents.ContainsKey(childSymbol))
+              parents[childSymbol] = new List<ISymbol>();
+            parents[childSymbol].Add(symbol);
+          }
+        }
+      }
+      // the topmost symbols have no parents
+      return parents.Values.SelectMany(x => x).Distinct().Where(x => !parents.ContainsKey(x));
+    }
+
+    private static IReadOnlyCollection<ISymbol> IterateBreadthReverse(this ISymbolicExpressionGrammarBase grammar, ISymbol topSymbol) {
+      // sort symbols in reverse breadth order (starting from the topSymbol)
+      // each symbol is visited only once (this avoids infinite recursion)
+      var symbols = new List<ISymbol> { topSymbol };
+      var visited = new HashSet<ISymbol> { topSymbol };
+      int i = 0;
+      while (i < symbols.Count) {
+        var symbol = symbols[i];
+        var minSubtreeCount = grammar.GetMinimumSubtreeCount(symbol);
+
+        for (int argIndex = 0; argIndex < minSubtreeCount; ++argIndex) {
+          foreach (var childSymbol in grammar.GetAllowedActiveSymbols(symbol, argIndex)) {
+            if (grammar.GetMinimumSubtreeCount(childSymbol) == 0)
+              continue;
+
+            if (visited.Add(childSymbol))
+              symbols.Add(childSymbol);
+          }
+        }
+        ++i;
+      }
+      symbols.Reverse();
+      return symbols;
+    }
+
+    private static IEnumerable<ISymbol> GetAllowedActiveSymbols(this ISymbolicExpressionGrammarBase grammar, ISymbol symbol, int argIndex) {
+      return grammar.GetAllowedChildSymbols(symbol, argIndex).Where(s => s.InitialFrequency > 0);
+    }
+
+    public static void CalculateMinimumExpressionLengths(ISymbolicExpressionGrammarBase grammar,
+      Dictionary<string, int> minimumExpressionLengths) {
+      minimumExpressionLengths.Clear();
+      //terminal symbols => minimum expression length = 1
+      foreach (var s in grammar.Symbols) {
+        if (grammar.GetMinimumSubtreeCount(s) == 0)
+          minimumExpressionLengths[s.Name] = 1;
+        else
+          minimumExpressionLengths[s.Name] = int.MaxValue;
+      }
+
+      foreach (var topSymbol in grammar.GetTopmostSymbols()) {
+        // get all symbols below in reverse breadth order
+        // this way we ensure lengths are calculated bottom-up
+        var symbols = grammar.IterateBreadthReverse(topSymbol);
+        foreach (var symbol in symbols) {
+          long minLength = 1;
+          for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
+            long length = grammar.GetAllowedActiveSymbols(symbol, argIndex)
+              .Where(x => minimumExpressionLengths.ContainsKey(x.Name))
+              .Select(x => minimumExpressionLengths[x.Name]).DefaultIfEmpty(int.MaxValue).Min();
+            minLength += length;
+          }
+          int oldLength;
+          if (minimumExpressionLengths.TryGetValue(symbol.Name, out oldLength))
+            minLength = Math.Min(minLength, oldLength);
+          minimumExpressionLengths[symbol.Name] = (int)Math.Min(int.MaxValue, minLength);
+        }
+        // correction step for cycles
+        bool changed = true;
+        while (changed) {
+          changed = false;
+          foreach (var symbol in symbols) {
+            long minLength = Enumerable.Range(0, grammar.GetMinimumSubtreeCount(symbol))
+              .Sum(x => grammar.GetAllowedActiveSymbols(symbol, x)
+              .Select(s => (long)minimumExpressionLengths[s.Name]).DefaultIfEmpty(int.MaxValue).Min()) + 1;
+            if (minLength < minimumExpressionLengths[symbol.Name]) {
+              minimumExpressionLengths[symbol.Name] = (int)Math.Min(minLength, int.MaxValue);
+              changed = true;
+            }
+          }
+        }
+      }
+    }
+
+    public static void CalculateMinimumExpressionDepth(ISymbolicExpressionGrammarBase grammar,
+      Dictionary<string, int> minimumExpressionDepths) {
+
+      minimumExpressionDepths.Clear();
+      //terminal symbols => minimum expression depth = 1
+      foreach (var s in grammar.Symbols) {
+        if (grammar.GetMinimumSubtreeCount(s) == 0)
+          minimumExpressionDepths[s.Name] = 1;
+        else
+          minimumExpressionDepths[s.Name] = int.MaxValue;
+      }
+
+      foreach (var topSymbol in grammar.GetTopmostSymbols()) {
+        // get all symbols below in reverse breadth order
+        // this way we ensure lengths are calculated bottom-up
+        var symbols = grammar.IterateBreadthReverse(topSymbol);
+        foreach (var symbol in symbols) {
+          long minDepth = -1;
+          for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
+            long depth = grammar.GetAllowedActiveSymbols(symbol, argIndex)
+              .Where(x => minimumExpressionDepths.ContainsKey(x.Name))
+              .Select(x => (long)minimumExpressionDepths[x.Name]).DefaultIfEmpty(int.MaxValue).Min() + 1;
+            minDepth = Math.Max(minDepth, depth);
+          }
+          int oldDepth;
+          if (minimumExpressionDepths.TryGetValue(symbol.Name, out oldDepth))
+            minDepth = Math.Min(minDepth, oldDepth);
+          minimumExpressionDepths[symbol.Name] = (int)Math.Min(int.MaxValue, minDepth);
+        }
+        // correction step for cycles
+        bool changed = true;
+        while (changed) {
+          changed = false;
+          foreach (var symbol in symbols) {
+            long minDepth = Enumerable.Range(0, grammar.GetMinimumSubtreeCount(symbol))
+              .Max(x => grammar.GetAllowedActiveSymbols(symbol, x)
+              .Select(s => (long)minimumExpressionDepths[s.Name]).DefaultIfEmpty(int.MaxValue).Min()) + 1;
+            if (minDepth < minimumExpressionDepths[symbol.Name]) {
+              minimumExpressionDepths[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
+              changed = true;
+            }
+          }
+        }
+      }
+    }
+  }
+}
Index: /stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/SymbolicExpressionGrammarBase.cs
===================================================================
--- /stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/SymbolicExpressionGrammarBase.cs	(revision 14957)
+++ /stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/SymbolicExpressionGrammarBase.cs	(revision 14958)
@@ -82,11 +82,4 @@
     protected SymbolicExpressionGrammarBase(bool deserializing)
       : base(deserializing) {
-      cachedMinExpressionLength = new Dictionary<string, int>();
-      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
-      cachedMinExpressionDepth = new Dictionary<string, int>();
-      cachedMaxExpressionDepth = new Dictionary<string, int>();
-
-      cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
-      cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
 
       symbols = new Dictionary<string, ISymbol>();
@@ -100,11 +93,4 @@
     protected SymbolicExpressionGrammarBase(SymbolicExpressionGrammarBase original, Cloner cloner)
       : base(original, cloner) {
-      cachedMinExpressionLength = new Dictionary<string, int>();
-      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
-      cachedMinExpressionDepth = new Dictionary<string, int>();
-      cachedMaxExpressionDepth = new Dictionary<string, int>();
-
-      cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
-      cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
 
       symbols = original.symbols.ToDictionary(x => x.Key, y => cloner.Clone(y.Value));
@@ -124,12 +110,4 @@
     protected SymbolicExpressionGrammarBase(string name, string description)
       : base(name, description) {
-      cachedMinExpressionLength = new Dictionary<string, int>();
-      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
-      cachedMinExpressionDepth = new Dictionary<string, int>();
-      cachedMaxExpressionDepth = new Dictionary<string, int>();
-
-      cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
-      cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
-
       symbols = new Dictionary<string, ISymbol>();
       symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>();
@@ -322,5 +300,5 @@
     }
 
-    private readonly Dictionary<Tuple<string, string>, bool> cachedIsAllowedChildSymbol;
+    private readonly Dictionary<Tuple<string, string>, bool> cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
     public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child) {
       if (allowedChildSymbols.Count == 0) return false;
@@ -352,5 +330,5 @@
     }
 
-    private readonly Dictionary<Tuple<string, string, int>, bool> cachedIsAllowedChildSymbolIndex;
+    private readonly Dictionary<Tuple<string, string, int>, bool> cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
     public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
       if (!child.Enabled) return false;
@@ -412,5 +390,5 @@
     }
 
-    private readonly Dictionary<string, int> cachedMinExpressionLength;
+    private readonly Dictionary<string, int> cachedMinExpressionLength = new Dictionary<string, int>();
     public int GetMinimumExpressionLength(ISymbol symbol) {
       int res;
@@ -423,29 +401,11 @@
         if (cachedMinExpressionLength.TryGetValue(symbol.Name, out res)) return res;
 
-        res = GetMinimumExpressionLengthRec(symbol);
-        foreach (var entry in cachedMinExpressionLength.Where(e => e.Value >= int.MaxValue).ToList()) {
-          if (entry.Key != symbol.Name) cachedMinExpressionLength.Remove(entry.Key);
-        }
-        return res;
-      }
-    }
-
-    private int GetMinimumExpressionLengthRec(ISymbol symbol) {
-      int temp;
-      if (!cachedMinExpressionLength.TryGetValue(symbol.Name, out temp)) {
-        cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
-        long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
-                                              let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
-                                                                      where s.InitialFrequency > 0.0
-                                                                      select GetMinimumExpressionLengthRec(s)).DefaultIfEmpty(0).Min()
-                                              select minForSlot).DefaultIfEmpty(0).Sum();
-
-        cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
+        GrammarUtils.CalculateMinimumExpressionLengths(this, cachedMinExpressionLength);
         return cachedMinExpressionLength[symbol.Name];
       }
-      return temp;
-    }
-
-    private readonly Dictionary<Tuple<string, int>, int> cachedMaxExpressionLength;
+    }
+
+
+    private readonly Dictionary<Tuple<string, int>, int> cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
     public int GetMaximumExpressionLength(ISymbol symbol, int maxDepth) {
       int temp;
@@ -469,5 +429,5 @@
     }
 
-    private readonly Dictionary<string, int> cachedMinExpressionDepth;
+    private readonly Dictionary<string, int> cachedMinExpressionDepth = new Dictionary<string, int>();
     public int GetMinimumExpressionDepth(ISymbol symbol) {
       int res;
@@ -480,27 +440,10 @@
         if (cachedMinExpressionDepth.TryGetValue(symbol.Name, out res)) return res;
 
-        res = GetMinimumExpressionDepthRec(symbol);
-        foreach (var entry in cachedMinExpressionDepth.Where(e => e.Value >= int.MaxValue).ToList()) {
-          if (entry.Key != symbol.Name) cachedMinExpressionDepth.Remove(entry.Key);
-        }
-        return res;
-      }
-    }
-    private int GetMinimumExpressionDepthRec(ISymbol symbol) {
-      int temp;
-      if (!cachedMinExpressionDepth.TryGetValue(symbol.Name, out temp)) {
-        cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
-        long minDepth = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
-                             let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
-                                                     where s.InitialFrequency > 0.0
-                                                     select GetMinimumExpressionDepthRec(s)).DefaultIfEmpty(0).Min()
-                             select minForSlot).DefaultIfEmpty(0).Max();
-        cachedMinExpressionDepth[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
+        GrammarUtils.CalculateMinimumExpressionDepth(this, cachedMinExpressionDepth);
         return cachedMinExpressionDepth[symbol.Name];
       }
-      return temp;
-    }
-
-    private readonly Dictionary<string, int> cachedMaxExpressionDepth;
+    }
+
+    private readonly Dictionary<string, int> cachedMaxExpressionDepth = new Dictionary<string, int>();
     public int GetMaximumExpressionDepth(ISymbol symbol) {
       int temp;
Index: /stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj
===================================================================
--- /stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj	(revision 14957)
+++ /stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj	(revision 14958)
@@ -129,4 +129,5 @@
     <Compile Include="ArchitectureManipulators\SubroutineDuplicater.cs" />
     <Compile Include="ArchitectureManipulators\SymbolicExpressionTreeArchitectureManipulator.cs" />
+    <Compile Include="Grammars\GrammarUtils.cs" />
     <Compile Include="SymbolicExpressionTreeProblem.cs" />
     <Compile Include="Compiler\Instruction.cs" />
Index: /stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Symbols/SimpleSymbol.cs
===================================================================
--- /stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Symbols/SimpleSymbol.cs	(revision 14957)
+++ /stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Symbols/SimpleSymbol.cs	(revision 14958)
@@ -61,4 +61,8 @@
     }
 
+    public SimpleSymbol(string name, int arity)
+      : this(name, string.Empty, arity, arity) {
+    }
+
     public SimpleSymbol(string name, string description, int minimumArity, int maximumArity)
       : base(name, description) {
Index: /stable/HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/GrammarsTest.cs
===================================================================
--- /stable/HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/GrammarsTest.cs	(revision 14958)
+++ /stable/HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/GrammarsTest.cs	(revision 14958)
@@ -0,0 +1,366 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System.Linq;
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+
+namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Tests {
+  [TestClass]
+  public class GrammarsTest {
+    [TestMethod]
+    [TestCategory("Encodings.SymbolicExpressionTree")]
+    [TestProperty("Time", "short")]
+    public void MinimumExpressionLengthTest() {
+      {
+        var grammar = CreateTestGrammar1();
+
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+
+        Assert.AreEqual(8, grammar.GetMinimumExpressionLength(prs));
+        Assert.AreEqual(7, grammar.GetMinimumExpressionLength(ss));
+        Assert.AreEqual(6, grammar.GetMinimumExpressionLength(x));
+      }
+
+      {
+        var grammar = CreateTestGrammar2();
+
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+
+        Assert.AreEqual(13, grammar.GetMinimumExpressionLength(prs));
+        Assert.AreEqual(12, grammar.GetMinimumExpressionLength(ss));
+        Assert.AreEqual(11, grammar.GetMinimumExpressionLength(x));
+      }
+
+      {
+        var grammar = CreateTestGrammar3();
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(prs));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(ss));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(x));
+      }
+
+      {
+        var grammar = CreateTestGrammar4();
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+        var y = grammar.Symbols.First(s => s.Name == "<y>");
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(prs));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(ss));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(x));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(y));
+      }
+
+      {
+        var grammar = CreateTestGrammar5();
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+        var y = grammar.Symbols.First(s => s.Name == "<y>");
+        Assert.AreEqual(5, grammar.GetMinimumExpressionLength(prs));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(ss));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(x));
+        Assert.AreEqual(2, grammar.GetMinimumExpressionLength(y));
+      }
+
+      {
+        var grammar = CreateTestGrammar6();
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+        var s_ = grammar.Symbols.First(s => s.Name == "<s>");
+        var a = grammar.Symbols.First(s => s.Name == "<a>");
+        var b = grammar.Symbols.First(s => s.Name == "<b>");
+        var c = grammar.Symbols.First(s => s.Name == "<c>");
+        var d = grammar.Symbols.First(s => s.Name == "<d>");
+        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(prs));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(ss));
+        Assert.AreEqual(2, grammar.GetMinimumExpressionLength(x));
+        Assert.AreEqual(5, grammar.GetMinimumExpressionLength(s_));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(a));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(b));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(c));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(d));
+      }
+    }
+
+    [TestMethod]
+    [TestCategory("Encodings.SymbolicExpressionTree")]
+    [TestProperty("Time", "short")]
+    public void MinimumExpressionDepthTest() {
+      {
+        var grammar = CreateTestGrammar1();
+
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var a = grammar.Symbols.First(s => s.Name == "<a>");
+        var b = grammar.Symbols.First(s => s.Name == "<b>");
+        var c = grammar.Symbols.First(s => s.Name == "<c>");
+        var d = grammar.Symbols.First(s => s.Name == "<d>");
+        var x = grammar.Symbols.First(s => s.Name == "x");
+        var y = grammar.Symbols.First(s => s.Name == "y");
+
+        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(prs));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(ss));
+        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(a));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(b));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(c));
+        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(d));
+        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(x));
+        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(y));
+      }
+
+      {
+        var grammar = CreateTestGrammar2();
+
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var a = grammar.Symbols.First(s => s.Name == "<a>");
+        var b = grammar.Symbols.First(s => s.Name == "<b>");
+        var c = grammar.Symbols.First(s => s.Name == "<c>");
+        var d = grammar.Symbols.First(s => s.Name == "<d>");
+        var x = grammar.Symbols.First(s => s.Name == "x");
+        var y = grammar.Symbols.First(s => s.Name == "y");
+
+        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(prs));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(ss));
+        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(a));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(b));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(c));
+        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(d));
+        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(x));
+        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(y));
+      }
+
+      {
+        var grammar = CreateTestGrammar3();
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(prs));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(ss));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(x));
+      }
+
+      {
+        var grammar = CreateTestGrammar4();
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+        var y = grammar.Symbols.First(s => s.Name == "<y>");
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(prs));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(ss));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(x));
+        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(y));
+      }
+
+      {
+        var grammar = CreateTestGrammar5();
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+        var y = grammar.Symbols.First(s => s.Name == "<y>");
+        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(prs));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(ss));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(x));
+        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(y));
+      }
+
+      {
+        var grammar = CreateTestGrammar6();
+        var prs = grammar.ProgramRootSymbol;
+        var ss = grammar.StartSymbol;
+        var x = grammar.Symbols.First(s => s.Name == "<x>");
+        var s_ = grammar.Symbols.First(s => s.Name == "<s>");
+        var a = grammar.Symbols.First(s => s.Name == "<a>");
+        var b = grammar.Symbols.First(s => s.Name == "<b>");
+        var c = grammar.Symbols.First(s => s.Name == "<c>");
+        var d = grammar.Symbols.First(s => s.Name == "<d>");
+        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(prs));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(ss));
+        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(x));
+        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(s_));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(a));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(b));
+        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(c));
+        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(d));
+      }
+    }
+
+    private static ISymbolicExpressionGrammar CreateTestGrammar1() {
+      var grammar = new SimpleSymbolicExpressionGrammar();
+      var x = new SimpleSymbol("<x>", 1);
+      var z = new SimpleSymbol("<z>", 6);
+      var a = new SimpleSymbol("<a>", 1);
+      var b = new SimpleSymbol("<b>", 1);
+      var c = new SimpleSymbol("<c>", 1);
+      var d = new SimpleSymbol("<d>", 1);
+
+      var _x = new SimpleSymbol("x", 0);
+      var _y = new SimpleSymbol("y", 0);
+
+      grammar.AddSymbol(x);
+      grammar.AddSymbol(z);
+      grammar.AddSymbol(a);
+      grammar.AddSymbol(b);
+      grammar.AddSymbol(c);
+      grammar.AddSymbol(d);
+      grammar.AddSymbol(_x);
+      grammar.AddSymbol(_y);
+
+      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
+      //uncommenting the line below changes the minimum expression length for the symbol <x>
+      grammar.AddAllowedChildSymbol(x, z);
+      grammar.AddAllowedChildSymbol(z, _x);
+      grammar.AddAllowedChildSymbol(x, a);
+      grammar.AddAllowedChildSymbol(a, b);
+      grammar.AddAllowedChildSymbol(b, c);
+      grammar.AddAllowedChildSymbol(c, d);
+      grammar.AddAllowedChildSymbol(d, _y);
+
+      return grammar;
+    }
+
+    private static ISymbolicExpressionGrammar CreateTestGrammar2() {
+      var grammar = new SimpleSymbolicExpressionGrammar();
+      var x = new SimpleSymbol("<x>", 2);
+      var z = new SimpleSymbol("<z>", 6);
+      var a = new SimpleSymbol("<a>", 1);
+      var b = new SimpleSymbol("<b>", 1);
+      var c = new SimpleSymbol("<c>", 1);
+      var d = new SimpleSymbol("<d>", 1);
+
+      var _x = new SimpleSymbol("x", 0);
+      var _y = new SimpleSymbol("y", 0);
+
+      grammar.AddSymbol(x);
+      grammar.AddSymbol(z);
+      grammar.AddSymbol(a);
+      grammar.AddSymbol(b);
+      grammar.AddSymbol(c);
+      grammar.AddSymbol(d);
+      grammar.AddSymbol(_x);
+      grammar.AddSymbol(_y);
+
+      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
+      //uncommenting the line below changes the minimum expression length for the symbol <x>
+      grammar.AddAllowedChildSymbol(x, z);
+      grammar.AddAllowedChildSymbol(z, _x);
+      grammar.AddAllowedChildSymbol(x, a);
+      grammar.AddAllowedChildSymbol(a, b);
+      grammar.AddAllowedChildSymbol(b, c);
+      grammar.AddAllowedChildSymbol(c, d);
+      grammar.AddAllowedChildSymbol(d, _y);
+
+      return grammar;
+    }
+
+    private static ISymbolicExpressionGrammar CreateTestGrammar3() {
+      var grammar = new SimpleSymbolicExpressionGrammar();
+      var x = new SimpleSymbol("<x>", 1);
+
+      grammar.AddSymbol(x);
+
+      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
+      grammar.AddAllowedChildSymbol(x, x);
+      return grammar;
+    }
+
+
+    private static ISymbolicExpressionGrammar CreateTestGrammar4() {
+      var grammar = new SimpleSymbolicExpressionGrammar();
+      var x = new SimpleSymbol("<x>", 1);
+      var y = new SimpleSymbol("<y>", 1);
+
+      grammar.AddSymbol(x);
+      grammar.AddSymbol(y);
+
+      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
+      grammar.AddAllowedChildSymbol(x, x);
+      grammar.AddAllowedChildSymbol(x, y);
+      grammar.AddAllowedChildSymbol(y, x);
+      grammar.AddAllowedChildSymbol(y, y);
+      return grammar;
+    }
+
+    private static ISymbolicExpressionGrammar CreateTestGrammar5() {
+      var grammar = new SimpleSymbolicExpressionGrammar();
+      var x = new SimpleSymbol("<x>", 1);
+      var y = new SimpleSymbol("<y>", 1);
+      var _x = new SimpleSymbol("x", 0);
+
+      grammar.AddSymbol(x);
+      grammar.AddSymbol(y);
+      grammar.AddSymbol(_x);
+
+      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
+      grammar.AddAllowedChildSymbol(x, x);
+      grammar.AddAllowedChildSymbol(x, y);
+      grammar.AddAllowedChildSymbol(y, x);
+      grammar.AddAllowedChildSymbol(y, y);
+      grammar.AddAllowedChildSymbol(y, _x);
+      return grammar;
+    }
+
+    private static ISymbolicExpressionGrammar CreateTestGrammar6() {
+      var grammar = new SimpleSymbolicExpressionGrammar();
+      var x = new SimpleSymbol("<x>", 1);
+      var s = new SimpleSymbol("<s>", 1);
+      var a = new SimpleSymbol("<a>", 1);
+      var b = new SimpleSymbol("<b>", 1);
+      var c = new SimpleSymbol("<c>", 1);
+      var d = new SimpleSymbol("<d>", 1);
+      var e = new SimpleSymbol("<e>", 1);
+
+      var _x = new SimpleSymbol("x", 0);
+      var _y = new SimpleSymbol("y", 0);
+
+      grammar.AddSymbol(x);
+      grammar.AddSymbol(s);
+      grammar.AddSymbol(a);
+      grammar.AddSymbol(b);
+      grammar.AddSymbol(c);
+      grammar.AddSymbol(d);
+      grammar.AddSymbol(e);
+      grammar.AddSymbol(_x);
+      grammar.AddSymbol(_y);
+
+      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
+      grammar.AddAllowedChildSymbol(x, s);
+      grammar.AddAllowedChildSymbol(x, _x);
+      grammar.AddAllowedChildSymbol(s, a);
+      grammar.AddAllowedChildSymbol(a, b);
+      grammar.AddAllowedChildSymbol(a, c);
+      grammar.AddAllowedChildSymbol(b, x);
+      grammar.AddAllowedChildSymbol(c, d);
+      grammar.AddAllowedChildSymbol(d, e);
+      grammar.AddAllowedChildSymbol(e, _y);
+
+      return grammar;
+    }
+  }
+}
Index: /stable/HeuristicLab.Tests/HeuristicLab.Tests.csproj
===================================================================
--- /stable/HeuristicLab.Tests/HeuristicLab.Tests.csproj	(revision 14957)
+++ /stable/HeuristicLab.Tests/HeuristicLab.Tests.csproj	(revision 14958)
@@ -559,4 +559,5 @@
     <Compile Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4\SubroutineDuplicaterTest.cs" />
     <Compile Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4\SubtreeCrossoverTest.cs" />
+    <Compile Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4\GrammarsTest.cs" />
     <Compile Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4\Util.cs" />
     <Compile Include="HeuristicLab.Persistence-3.3\StorableAttributeTests.cs" />
