Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln	(revision 11659)
@@ -0,0 +1,38 @@
+﻿
+Microsoft Visual Studio Solution File, Format Version 12.00
+# Visual Studio 2012
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.GrammaticalOptimization", "HeuristicLab.Problems.GrammaticalOptimization\HeuristicLab.Problems.GrammaticalOptimization.csproj", "{CB9DCCF6-667E-4A13-B82D-DBD6B45A045E}"
+EndProject
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.GrammaticalOptimization.Test", "HeuristicLab.Problems.GrammaticalOptimization.Test\HeuristicLab.Problems.GrammaticalOptimization.Test.csproj", "{3FB49880-7127-40D4-A9D3-A6C30BDDE885}"
+EndProject
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Algorithms.GrammaticalOptimization", "HeuristicLab.Algorithms.GrammaticalOptimization\HeuristicLab.Algorithms.GrammaticalOptimization.csproj", "{EEA07488-1A51-412A-A52C-53B754A628B3}"
+EndProject
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Main", "Main\Main.csproj", "{524CBD70-6F99-46AF-AD00-A0BC9FD1175B}"
+EndProject
+Global
+	GlobalSection(SolutionConfigurationPlatforms) = preSolution
+		Debug|Any CPU = Debug|Any CPU
+		Release|Any CPU = Release|Any CPU
+	EndGlobalSection
+	GlobalSection(ProjectConfigurationPlatforms) = postSolution
+		{CB9DCCF6-667E-4A13-B82D-DBD6B45A045E}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+		{CB9DCCF6-667E-4A13-B82D-DBD6B45A045E}.Debug|Any CPU.Build.0 = Debug|Any CPU
+		{CB9DCCF6-667E-4A13-B82D-DBD6B45A045E}.Release|Any CPU.ActiveCfg = Release|Any CPU
+		{CB9DCCF6-667E-4A13-B82D-DBD6B45A045E}.Release|Any CPU.Build.0 = Release|Any CPU
+		{3FB49880-7127-40D4-A9D3-A6C30BDDE885}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+		{3FB49880-7127-40D4-A9D3-A6C30BDDE885}.Debug|Any CPU.Build.0 = Debug|Any CPU
+		{3FB49880-7127-40D4-A9D3-A6C30BDDE885}.Release|Any CPU.ActiveCfg = Release|Any CPU
+		{3FB49880-7127-40D4-A9D3-A6C30BDDE885}.Release|Any CPU.Build.0 = Release|Any CPU
+		{EEA07488-1A51-412A-A52C-53B754A628B3}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+		{EEA07488-1A51-412A-A52C-53B754A628B3}.Debug|Any CPU.Build.0 = Debug|Any CPU
+		{EEA07488-1A51-412A-A52C-53B754A628B3}.Release|Any CPU.ActiveCfg = Release|Any CPU
+		{EEA07488-1A51-412A-A52C-53B754A628B3}.Release|Any CPU.Build.0 = Release|Any CPU
+		{524CBD70-6F99-46AF-AD00-A0BC9FD1175B}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+		{524CBD70-6F99-46AF-AD00-A0BC9FD1175B}.Debug|Any CPU.Build.0 = Debug|Any CPU
+		{524CBD70-6F99-46AF-AD00-A0BC9FD1175B}.Release|Any CPU.ActiveCfg = Release|Any CPU
+		{524CBD70-6F99-46AF-AD00-A0BC9FD1175B}.Release|Any CPU.Build.0 = Release|Any CPU
+	EndGlobalSection
+	GlobalSection(SolutionProperties) = preSolution
+		HideSolutionNode = FALSE
+	EndGlobalSection
+EndGlobal
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj	(revision 11659)
@@ -0,0 +1,62 @@
+﻿<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="4.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <Import Project="$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props" Condition="Exists('$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props')" />
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <ProjectGuid>{EEA07488-1A51-412A-A52C-53B754A628B3}</ProjectGuid>
+    <OutputType>Library</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <RootNamespace>HeuristicLab.Algorithms.GrammaticalOptimization</RootNamespace>
+    <AssemblyName>HeuristicLab.Algorithms.GrammaticalOptimization</AssemblyName>
+    <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
+    <FileAlignment>512</FileAlignment>
+    <TargetFrameworkProfile />
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+    <DebugSymbols>true</DebugSymbols>
+    <DebugType>full</DebugType>
+    <Optimize>false</Optimize>
+    <OutputPath>bin\Debug\</OutputPath>
+    <DefineConstants>DEBUG;TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+    <Prefer32Bit>false</Prefer32Bit>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+    <OutputPath>bin\Release\</OutputPath>
+    <DefineConstants>TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+    <Prefer32Bit>false</Prefer32Bit>
+  </PropertyGroup>
+  <ItemGroup>
+    <Reference Include="System" />
+    <Reference Include="System.Core" />
+    <Reference Include="System.Xml.Linq" />
+    <Reference Include="System.Data.DataSetExtensions" />
+    <Reference Include="Microsoft.CSharp" />
+    <Reference Include="System.Data" />
+    <Reference Include="System.Xml" />
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="RandomSearch.cs" />
+  </ItemGroup>
+  <ItemGroup>
+    <ProjectReference Include="..\HeuristicLab.Problems.GrammaticalOptimization\HeuristicLab.Problems.GrammaticalOptimization.csproj">
+      <Project>{cb9dccf6-667e-4a13-b82d-dbd6b45a045e}</Project>
+      <Name>HeuristicLab.Problems.GrammaticalOptimization</Name>
+    </ProjectReference>
+  </ItemGroup>
+  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
+  <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 
+       Other similar extension points exist, see Microsoft.Common.targets.
+  <Target Name="BeforeBuild">
+  </Target>
+  <Target Name="AfterBuild">
+  </Target>
+  -->
+</Project>
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Properties/AssemblyInfo.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Properties/AssemblyInfo.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Properties/AssemblyInfo.cs	(revision 11659)
@@ -0,0 +1,36 @@
+﻿using System.Reflection;
+using System.Runtime.CompilerServices;
+using System.Runtime.InteropServices;
+
+// General Information about an assembly is controlled through the following 
+// set of attributes. Change these attribute values to modify the information
+// associated with an assembly.
+[assembly: AssemblyTitle("HeuristicLab.Algorithms.GrammaticalOptimization")]
+[assembly: AssemblyDescription("")]
+[assembly: AssemblyConfiguration("")]
+[assembly: AssemblyCompany("Microsoft")]
+[assembly: AssemblyProduct("HeuristicLab.Algorithms.GrammaticalOptimization")]
+[assembly: AssemblyCopyright("Copyright © Microsoft 2014")]
+[assembly: AssemblyTrademark("")]
+[assembly: AssemblyCulture("")]
+
+// Setting ComVisible to false makes the types in this assembly not visible 
+// to COM components.  If you need to access a type in this assembly from 
+// COM, set the ComVisible attribute to true on that type.
+[assembly: ComVisible(false)]
+
+// The following GUID is for the ID of the typelib if this project is exposed to COM
+[assembly: Guid("074345f1-0e24-4ab7-8a24-ace6874d162b")]
+
+// Version information for an assembly consists of the following four values:
+//
+//      Major Version
+//      Minor Version 
+//      Build Number
+//      Revision
+//
+// You can specify all the values or you can default the Build and Revision Numbers 
+// by using the '*' as shown below:
+// [assembly: AssemblyVersion("1.0.*")]
+[assembly: AssemblyVersion("1.0.0.0")]
+[assembly: AssemblyFileVersion("1.0.0.0")]
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/RandomSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/RandomSearch.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/RandomSearch.cs	(revision 11659)
@@ -0,0 +1,48 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.GrammaticalOptimization {
+  public class RandomSearch {
+    public event Action<string, double> FoundNewBestSolution;
+    public event Action<string, double> SolutionEvaluated;
+
+    private readonly int maxLen;
+    private readonly Random random;
+
+    public RandomSearch(int maxLen) {
+      this.maxLen = maxLen;
+      this.random = new Random(31415);
+    }
+
+    public void Run(IProblem problem, int maxIterations) {
+      double bestQuality = double.MinValue;
+      for (int i = 0; i < maxIterations; i++) {
+        var sentence = CreateSentence(problem.Grammar);
+        var quality = problem.Evaluate(sentence);
+        RaiseSolutionEvaluated(sentence, quality);
+
+        if (quality > bestQuality) {
+          bestQuality = quality;
+          RaiseFoundNewBestSolution(sentence, quality);
+        }
+      }
+    }
+
+    private string CreateSentence(IGrammar grammar) {
+      var sentence = grammar.SentenceSymbol.ToString();
+      return grammar.CompleteSentenceRandomly(random, sentence, maxLen);
+    }
+
+    private void RaiseSolutionEvaluated(string sentence, double quality) {
+      var handler = SolutionEvaluated;
+      if (handler != null) handler(sentence, quality);
+    }
+    private void RaiseFoundNewBestSolution(string sentence, double quality) {
+      var handler = FoundNewBestSolution;
+      if (handler != null) handler(sentence, quality);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/HeuristicLab.Problems.GrammaticalOptimization.Test.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/HeuristicLab.Problems.GrammaticalOptimization.Test.csproj	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/HeuristicLab.Problems.GrammaticalOptimization.Test.csproj	(revision 11659)
@@ -0,0 +1,95 @@
+﻿<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="4.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <ProjectGuid>{3FB49880-7127-40D4-A9D3-A6C30BDDE885}</ProjectGuid>
+    <OutputType>Library</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <RootNamespace>HeuristicLab.Problems.GrammaticalOptimization.Test</RootNamespace>
+    <AssemblyName>HeuristicLab.Problems.GrammaticalOptimization.Test</AssemblyName>
+    <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
+    <FileAlignment>512</FileAlignment>
+    <ProjectTypeGuids>{3AC096D0-A1C2-E12C-1390-A8335801FDAB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}</ProjectTypeGuids>
+    <VisualStudioVersion Condition="'$(VisualStudioVersion)' == ''">10.0</VisualStudioVersion>
+    <VSToolsPath Condition="'$(VSToolsPath)' == ''">$(MSBuildExtensionsPath32)\Microsoft\VisualStudio\v$(VisualStudioVersion)</VSToolsPath>
+    <ReferencePath>$(ProgramFiles)\Common Files\microsoft shared\VSTT\$(VisualStudioVersion)\UITestExtensionPackages</ReferencePath>
+    <IsCodedUITest>False</IsCodedUITest>
+    <TestProjectType>UnitTest</TestProjectType>
+    <TargetFrameworkProfile />
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+    <DebugSymbols>true</DebugSymbols>
+    <DebugType>full</DebugType>
+    <Optimize>false</Optimize>
+    <OutputPath>bin\Debug\</OutputPath>
+    <DefineConstants>DEBUG;TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+    <Prefer32Bit>false</Prefer32Bit>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+    <OutputPath>bin\Release\</OutputPath>
+    <DefineConstants>TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+    <Prefer32Bit>false</Prefer32Bit>
+  </PropertyGroup>
+  <ItemGroup>
+    <Reference Include="System" />
+    <Reference Include="System.Core">
+      <RequiredTargetFramework>3.5</RequiredTargetFramework>
+    </Reference>
+  </ItemGroup>
+  <Choose>
+    <When Condition="('$(VisualStudioVersion)' == '10.0' or '$(VisualStudioVersion)' == '') and '$(TargetFrameworkVersion)' == 'v3.5'">
+      <ItemGroup>
+        <Reference Include="Microsoft.VisualStudio.QualityTools.UnitTestFramework, Version=10.1.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL" />
+      </ItemGroup>
+    </When>
+    <Otherwise>
+      <ItemGroup>
+        <Reference Include="Microsoft.VisualStudio.QualityTools.UnitTestFramework" />
+      </ItemGroup>
+    </Otherwise>
+  </Choose>
+  <ItemGroup>
+    <Compile Include="TestInstances.cs" />
+    <Compile Include="Properties\AssemblyInfo.cs" />
+  </ItemGroup>
+  <ItemGroup>
+    <ProjectReference Include="..\HeuristicLab.Problems.GrammaticalOptimization\HeuristicLab.Problems.GrammaticalOptimization.csproj">
+      <Project>{cb9dccf6-667e-4a13-b82d-dbd6b45a045e}</Project>
+      <Name>HeuristicLab.Problems.GrammaticalOptimization</Name>
+    </ProjectReference>
+  </ItemGroup>
+  <Choose>
+    <When Condition="'$(VisualStudioVersion)' == '10.0' And '$(IsCodedUITest)' == 'True'">
+      <ItemGroup>
+        <Reference Include="Microsoft.VisualStudio.QualityTools.CodedUITestFramework, Version=10.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL">
+          <Private>False</Private>
+        </Reference>
+        <Reference Include="Microsoft.VisualStudio.TestTools.UITest.Common, Version=10.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL">
+          <Private>False</Private>
+        </Reference>
+        <Reference Include="Microsoft.VisualStudio.TestTools.UITest.Extension, Version=10.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL">
+          <Private>False</Private>
+        </Reference>
+        <Reference Include="Microsoft.VisualStudio.TestTools.UITesting, Version=10.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL">
+          <Private>False</Private>
+        </Reference>
+      </ItemGroup>
+    </When>
+  </Choose>
+  <Import Project="$(VSToolsPath)\TeamTest\Microsoft.TestTools.targets" Condition="Exists('$(VSToolsPath)\TeamTest\Microsoft.TestTools.targets')" />
+  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
+  <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 
+       Other similar extension points exist, see Microsoft.Common.targets.
+  <Target Name="BeforeBuild">
+  </Target>
+  <Target Name="AfterBuild">
+  </Target>
+  -->
+</Project>
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/Properties/AssemblyInfo.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/Properties/AssemblyInfo.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/Properties/AssemblyInfo.cs	(revision 11659)
@@ -0,0 +1,36 @@
+﻿using System.Reflection;
+using System.Runtime.CompilerServices;
+using System.Runtime.InteropServices;
+
+// General Information about an assembly is controlled through the following 
+// set of attributes. Change these attribute values to modify the information
+// associated with an assembly.
+[assembly: AssemblyTitle("HeuristicLab.Problems.GrammaticalOptimization.Test")]
+[assembly: AssemblyDescription("")]
+[assembly: AssemblyConfiguration("")]
+[assembly: AssemblyCompany("Microsoft")]
+[assembly: AssemblyProduct("HeuristicLab.Problems.GrammaticalOptimization.Test")]
+[assembly: AssemblyCopyright("Copyright © Microsoft 2014")]
+[assembly: AssemblyTrademark("")]
+[assembly: AssemblyCulture("")]
+
+// Setting ComVisible to false makes the types in this assembly not visible 
+// to COM components.  If you need to access a type in this assembly from 
+// COM, set the ComVisible attribute to true on that type.
+[assembly: ComVisible(false)]
+
+// The following GUID is for the ID of the typelib if this project is exposed to COM
+[assembly: Guid("1f7e7cac-1ef2-43dc-b5da-5547058c9309")]
+
+// Version information for an assembly consists of the following four values:
+//
+//      Major Version
+//      Minor Version 
+//      Build Number
+//      Revision
+//
+// You can specify all the values or you can default the Build and Revision Numbers 
+// by using the '*' as shown below:
+// [assembly: AssemblyVersion("1.0.*")]
+[assembly: AssemblyVersion("1.0.0.0")]
+[assembly: AssemblyFileVersion("1.0.0.0")]
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestInstances.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestInstances.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestInstances.cs	(revision 11659)
@@ -0,0 +1,255 @@
+﻿using System;
+using System.Diagnostics;
+using System.Linq;
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
+  [TestClass]
+  public class TestInstances {
+    [TestMethod]
+    public void TestGrammarFromString() {
+      {
+        var g = Grammar.FromString(@"
+
+G(S):
+  S -> aA | bB
+  A -> a | aA
+  B -> Bb | b
+");
+        Assert.AreEqual('S', g.SentenceSymbol);
+        Assert.AreEqual(2, g.TerminalSymbols.Count());
+        Assert.AreEqual(3, g.NonTerminalSymbols.Count());
+        Assert.IsTrue(g.TerminalSymbols.All(s => new char[] { 'a', 'b' }.Contains(s)));
+        Assert.IsTrue(g.NonTerminalSymbols.All(s => new char[] { 'S', 'A', 'B' }.Contains(s)));
+
+        Assert.AreEqual(2, g.GetAlternatives('S').Count());
+        Assert.AreEqual(2, g.GetAlternatives('A').Count());
+        Assert.AreEqual(2, g.GetAlternatives('B').Count());
+
+        Assert.IsTrue(g.GetAlternatives('S').Contains("aA"));
+        Assert.IsTrue(g.GetAlternatives('S').Contains("bB"));
+        Assert.IsTrue(g.GetAlternatives('A').Contains("aA"));
+        Assert.IsTrue(g.GetAlternatives('A').Contains("a"));
+        Assert.IsTrue(g.GetAlternatives('B').Contains("Bb"));
+        Assert.IsTrue(g.GetAlternatives('B').Contains("b"));
+
+        Assert.AreEqual(2, g.MinPhraseLength("S"));
+        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength("S"));
+        Assert.AreEqual(1, g.MinPhraseLength("A"));
+        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength("A"));
+        Assert.AreEqual(1, g.MinPhraseLength("B"));
+        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength("B"));
+      }
+
+      {
+        var g = Grammar.FromString(@"
+
+G(S):
+  S -> sS
+");
+        Assert.AreEqual('S', g.SentenceSymbol);
+        Assert.AreEqual(1, g.TerminalSymbols.Count());
+        Assert.AreEqual(1, g.NonTerminalSymbols.Count());
+        Assert.IsTrue(g.TerminalSymbols.All(s => new char[] { 's' }.Contains(s)));
+        Assert.IsTrue(g.NonTerminalSymbols.All(s => new char[] { 'S' }.Contains(s)));
+
+        Assert.AreEqual(1, g.GetAlternatives('S').Count());
+
+        Assert.IsTrue(g.GetAlternatives('S').Contains("sS"));
+
+        Assert.AreEqual(short.MaxValue, g.MinPhraseLength("S"));
+        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength("S"));
+      }
+
+      {
+        var g = Grammar.FromString(@"
+
+G(S):
+S->sss|sS");
+        Assert.AreEqual('S', g.SentenceSymbol);
+        Assert.AreEqual(1, g.TerminalSymbols.Count());
+        Assert.AreEqual(1, g.NonTerminalSymbols.Count());
+        Assert.IsTrue(g.TerminalSymbols.All(s => new char[] { 's' }.Contains(s)));
+        Assert.IsTrue(g.NonTerminalSymbols.All(s => new char[] { 'S' }.Contains(s)));
+
+        Assert.AreEqual(2, g.GetAlternatives('S').Count());
+
+        Assert.IsTrue(g.GetAlternatives('S').Contains("sss"));
+        Assert.IsTrue(g.GetAlternatives('S').Contains("sS"));
+
+        Assert.AreEqual(3, g.MinPhraseLength("S"));
+        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength("S"));
+        Assert.AreEqual(4, g.MinPhraseLength("sS"));
+        Assert.AreEqual(7, g.MinPhraseLength("sSS"));
+        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength("sSS"));
+        Assert.AreEqual(3, g.MaxPhraseLength("sss"));
+        Assert.AreEqual(3, g.MinPhraseLength("sss"));
+      }
+
+      {
+        var g = Grammar.FromString(@"
+
+G(S):
+S->T|TS
+T-> a..z
+");
+        Assert.AreEqual('S', g.SentenceSymbol);
+        Assert.AreEqual(26, g.TerminalSymbols.Count());
+        Assert.AreEqual(2, g.NonTerminalSymbols.Count());
+        Assert.IsTrue(g.NonTerminalSymbols.All(s => new char[] { 'S', 'T' }.Contains(s)));
+
+        Assert.AreEqual(2, g.GetAlternatives('S').Count());
+
+        Assert.IsTrue(g.GetAlternatives('S').Contains("T"));
+        Assert.IsTrue(g.GetAlternatives('S').Contains("TS"));
+
+        Assert.AreEqual(1, g.MinPhraseLength("S"));
+        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength("S"));
+        Assert.AreEqual(1, g.MinPhraseLength("T"));
+        Assert.AreEqual(1, g.MaxPhraseLength("T"));
+      }
+
+    }
+
+    [TestMethod]
+    public void TestRoyalSymbolProblem() {
+      var p = new RoyalSymbolProblem();
+      Console.WriteLine(p.Grammar);
+
+      Assert.AreEqual(1, p.Evaluate("ab"));
+      Assert.AreEqual(0, p.Evaluate("bb"));
+      Assert.AreEqual(2, p.Evaluate("aa"));
+      Assert.AreEqual(3, p.Evaluate("aaa"));
+    }
+
+
+    [TestMethod]
+    public void TestRoyalPairProblem() {
+      var p = new RoyalPairProblem();
+      Console.WriteLine(p.Grammar);
+
+      Assert.AreEqual(1, p.Evaluate("ab"));
+      Assert.AreEqual(0, p.Evaluate("bb"));
+      Assert.AreEqual(0, p.Evaluate("aa"));
+      Assert.AreEqual(0, p.Evaluate("aaa"));
+      Assert.AreEqual(2, p.Evaluate("aba"));
+      Assert.AreEqual(2, p.Evaluate("abba"));
+      Assert.AreEqual(3, p.Evaluate("abab"));
+    }
+
+    [TestMethod]
+    public void TestSantaFeAntProblem() {
+      var p = new SantaFeAntProblem();
+      Console.WriteLine(p.Grammar);
+
+      // one possible optimal solution: if-food-ahead (move) ( left left if-food-ahead (move) (right)) move right
+      Assert.AreEqual(89, p.Evaluate("?(m)(ll?(m)(r))mr"));
+    }
+    [TestMethod]
+    public void TestRoyalTreeProblem() {
+      var p = new RoyalTreeProblem();
+      Console.WriteLine(p.Grammar);
+
+    }
+    [TestMethod]
+    public void TestRoyalRoadProblem() {
+      var p = new RoyalRoadProblem();
+      Console.WriteLine(p.Grammar);
+
+    }
+    [TestMethod]
+    public void TestPalindromeProblem() {
+      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("aba"));
+      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("aaba"));
+      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("abaa"));
+      Assert.AreEqual("aabaa", PalindromeProblem.LongestPalindromicSubstring("aaaabaa"));
+      Assert.AreEqual("aabaa", PalindromeProblem.LongestPalindromicSubstring("aabaaaa"));
+      Assert.AreEqual("baaaab", PalindromeProblem.LongestPalindromicSubstring("aabaaaab"));
+
+
+      var p = new PalindromeProblem();
+      Console.WriteLine(p.Grammar);
+
+      Assert.AreEqual(1, p.Evaluate("a"));
+      Assert.AreEqual(2, p.Evaluate("aa"));
+      Assert.AreEqual(3, p.Evaluate("aaa"));
+      Assert.AreEqual(3, p.Evaluate("aba"));
+      Assert.AreEqual(3, p.Evaluate("baba"));
+      Assert.AreEqual(3, p.Evaluate("abab"));
+      Assert.AreEqual(5, p.Evaluate("babab"));
+    }
+    [TestMethod]
+    public void TestHardPalindromeProblem() {
+      var p = new HardPalindromeProblem();
+      Console.WriteLine(p.Grammar);
+
+      Assert.AreEqual(1 + 1, p.Evaluate("a"));
+      Assert.AreEqual(2 + 1, p.Evaluate("aa"));
+      Assert.AreEqual(3 + 1, p.Evaluate("aaa"));
+      Assert.AreEqual(3 + 2, p.Evaluate("aba"));
+      Assert.AreEqual(3 + 2, p.Evaluate("baba"));
+      Assert.AreEqual(3 + 2, p.Evaluate("abab"));
+      Assert.AreEqual(5 + 2, p.Evaluate("babab"));
+      Assert.AreEqual(5 + 3, p.Evaluate("bacab"));
+    }
+
+    [TestMethod]
+    public void TestEvenParityProblem() {
+      var p = new EvenParityProblem();
+      Console.WriteLine(p.Grammar);
+
+      // a | b | c | d | res
+      // 0 | 0 | 0 | 0 | 1
+      // 0 | 0 | 0 | 1 | 0
+      // 0 | 0 | 1 | 0 | 0
+      // 0 | 0 | 1 | 1 | 1
+      // 0 | 1 | 0 | 0 | 0
+      // 0 | 1 | 0 | 1 | 1
+      // 0 | 1 | 1 | 0 | 1
+      // 0 | 1 | 1 | 1 | 0
+      // 1 | 0 | 0 | 0 | 0
+      // 1 | 0 | 0 | 1 | 1
+      // 1 | 0 | 1 | 0 | 1
+      // 1 | 0 | 1 | 1 | 0
+      // 1 | 1 | 0 | 0 | 1
+      // 1 | 1 | 0 | 1 | 0
+      // 1 | 1 | 1 | 0 | 0
+      // 1 | 1 | 1 | 1 | 1
+
+
+      Assert.AreEqual(8, p.Evaluate("a"));
+      Assert.AreEqual(8, p.Evaluate("b"));
+      Assert.AreEqual(8, p.Evaluate("c"));
+      Assert.AreEqual(8, p.Evaluate("d"));
+
+      Assert.AreEqual(8, p.Evaluate("a*b")); // a and b
+      Assert.AreEqual(8, p.Evaluate("a+b")); // a or b
+      Assert.AreEqual(8, p.Evaluate("!a*b+a*!b")); // a xor b
+      Assert.AreEqual(8, p.Evaluate("!(a*b)+(a*!b)")); // a xor b
+      Assert.AreEqual(16, p.Evaluate("a^b^c^d")); // a xor b
+    }
+
+    [TestMethod]
+    public void TestSymbolicRegressionPoly10Problem() {
+      var p = new SymbolicRegressionPoly10Problem();
+      Console.WriteLine(p.Grammar);
+
+      Assert.AreEqual(0.00319925877644673, p.Evaluate("a"), 1.0E-7);
+      Assert.AreEqual(0.00632775454329686, p.Evaluate("b"), 1.0E-7);
+      Assert.AreEqual(0.00569030954291292, p.Evaluate("c"), 1.0E-7);
+      Assert.AreEqual(3.32317092313123E-05, p.Evaluate("d"), 1.0E-7);
+      Assert.AreEqual(0.000562538829174826, p.Evaluate("e"), 1.0E-7);
+      Assert.AreEqual(3.29458942533772E-06, p.Evaluate("f"), 1.0E-7);
+      Assert.AreEqual(0.000193866006166768, p.Evaluate("g"), 1.0E-7);
+      Assert.AreEqual(2.83339004096246E-05, p.Evaluate("h"), 1.0E-7);
+      Assert.AreEqual(0.00291584574914239, p.Evaluate("i"), 1.0E-7);
+      Assert.AreEqual(0.00504038616701691, p.Evaluate("j"), 1.0E-7);
+
+      Assert.AreEqual(0.252718466940018, p.Evaluate("a*b"), 1.0E-7);
+      Assert.AreEqual(0.00173739472363473, p.Evaluate("b*c"), 1.0E-7);
+      Assert.AreEqual(3.15450564064128E-05, p.Evaluate("d*e"), 1.0E-7);
+
+      Assert.AreEqual(1.0, p.Evaluate("a*b+c*d+e*f+a*g*i+c*f*j"), 1.0E-7);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/EvenParityProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/EvenParityProblem.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/EvenParityProblem.cs	(revision 11659)
@@ -0,0 +1,53 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Text.RegularExpressions;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  // 4-bit even parity
+  public class EvenParityProblem : IProblem {
+    // + == OR
+    // * == AND
+    private const string grammarString = @"
+G(S):
+S -> N | N*S | N+S | !S | (S)
+N -> a | b | c | d
+";
+
+    private readonly IGrammar grammar;
+    private readonly ExpressionInterpreter interpreter = new ExpressionInterpreter();
+    public EvenParityProblem() {
+      this.grammar = new Grammar(grammarString);
+    }
+
+    public double GetBestKnownQuality(int maxLen) {
+      // for now only an upper bound is returned, ideally all fitness cases are predicted correctly
+      return Math.Pow(2, 4);
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      var vars = new bool[4];
+      var nCorrect = 0;
+      for (int b0 = 0; b0 <= 1; b0++)
+        for (int b1 = 0; b1 <= 1; b1++)
+          for (int b2 = 0; b2 <= 1; b2++)
+            for (int b3 = 0; b3 <= 1; b3++) {
+              vars[0] = b0 > 0;
+              vars[1] = b1 > 0;
+              vars[2] = b2 > 0;
+              vars[3] = b3 > 0;
+
+              var pred = interpreter.Interpret(sentence, vars);
+              var target = (b0 > 0) ^ (b1 > 0) ^ (b2 > 0) ^ (b3 > 0);
+              if (pred == target) nCorrect++;
+            }
+      return nCorrect;
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs	(revision 11659)
@@ -0,0 +1,106 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics.Eventing.Reader;
+using System.Linq;
+using System.Runtime.Remoting.Messaging;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public class ExpressionInterpreter {
+    private string sentence;
+    private int syIdx;
+    // interprets sentences from L(G(Expr)):
+    // Expr -> Term { ('+' | '-' | '^' ) Term } 
+    // Term -> Fact { ('*' | '/') Fact }
+    // Fact -> '!' Expr | '(' Expr ')' | Var
+    // Var -> 'a'..'z'
+
+    // for boolean problems the symbol * representes the AND operator, the symbol + represents the OR operator, ! = NOT, ^ = XOR
+
+    public bool Interpret(string sentence, bool[] vars) {
+      InitLex(sentence);
+      var d = new double[vars.Length];
+      for (int i = 0; i < vars.Length; i++) d[i] = vars[i] ? 1.0 : 0.0;
+      return !(Expr(d).IsAlmost(0));
+    }
+
+    public double Interpret(string sentence, double[] vars) {
+      InitLex(sentence);
+      return Expr(vars);
+    }
+
+
+    private void InitLex(string sentence) {
+      this.sentence = sentence;
+      this.syIdx = 0;
+    }
+
+    private char CurSy() {
+      if (syIdx >= sentence.Length) return '\0';
+      return sentence[syIdx];
+    }
+    private void NewSy() {
+      if (syIdx < sentence.Length) syIdx++;
+    }
+
+    // helper for xor
+    private double Not(double x) {
+      return x.IsAlmost(0) ? 1.0 : 0.0;
+    }
+
+    private double Expr(double[] d) {
+      var r = 0.0;
+      r = Term(d);
+      while (CurSy() == '+' || CurSy() == '-' || CurSy() == '^') {
+        if (CurSy() == '+') {
+          NewSy();
+          r += Expr(d);
+        } else if (CurSy() == '-') {
+          NewSy();
+          r -= Expr(d);
+        } else if (CurSy() == '^') {
+          NewSy();
+          var e = Expr(d);
+          r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y)
+        }
+      }
+      return r;
+    }
+
+    private double Term(double[] d) {
+      var r = 0.0;
+      r = Fact(d);
+      while (CurSy() == '*' || CurSy() == '/') {
+        if (CurSy() == '*') {
+          NewSy();
+          r *= Term(d);
+        } else if (CurSy() == '/') {
+          NewSy();
+          r /= Term(d);
+        }
+      }
+      return r;
+    }
+
+    private double Fact(double[] d) {
+      double r = 0.0;
+      if (CurSy() == '!') {
+        NewSy();
+        r = Not(Expr(d));
+      } else if (CurSy() == '(') {
+        NewSy();
+        r = Expr(d);
+        if (CurSy() != ')') throw new ArgumentException();
+        NewSy();
+      } else if (CurSy() >= 'a' && CurSy() <= 'z') {
+        int o = Convert.ToByte(CurSy()) - Convert.ToByte('a');
+        if (o < 0 || o >= d.Length) throw new ArgumentException();
+        r = d[o];
+        NewSy();
+      } else throw new ArgumentException();
+      return r;
+    }
+
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Extensions.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Extensions.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Extensions.cs	(revision 11659)
@@ -0,0 +1,18 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public static class Extensions {
+    public static bool IsAlmost(this double x, double y) {
+      return Math.Abs(x - y) < 1.0e-6;
+    }
+
+    public static T SelectRandom<T>(this IEnumerable<T> xs, Random rand) {
+      var xsArr = xs.ToArray();
+      return xsArr[rand.Next(xsArr.Length)];
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs	(revision 11659)
@@ -0,0 +1,271 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Data;
+using System.Diagnostics;
+using System.IO;
+using System.Linq;
+using System.Text;
+using System.Text.RegularExpressions;
+using System.Xml.Linq;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+
+  // phrases and symbols are both strings
+  // spaces are used to separate symbols in phases
+  // terminal and non-terminal symbols must not contain white-space
+  // white-spaces are not counted when determining the length of a sentence, only the number of terminal symbols is relevant
+
+  public class Grammar : IGrammar {
+
+    private readonly Dictionary<char, List<string>> rules;
+    private readonly HashSet<char> terminalSymbols;
+    private readonly char sentenceSymbol;
+    private readonly HashSet<char> nonTerminalSymbols;
+    private readonly Dictionary<string, int> maxPhraseLength = new Dictionary<string, int>();
+    private readonly Dictionary<string, int> minPhraseLength = new Dictionary<string, int>();
+
+    public char SentenceSymbol { get { return sentenceSymbol; } }
+    public IEnumerable<char> NonTerminalSymbols { get { return nonTerminalSymbols; } }
+    public IEnumerable<char> TerminalSymbols { get { return terminalSymbols; } }
+    public IEnumerable<char> Symbols { get { return nonTerminalSymbols.Concat(terminalSymbols); } } // ctor guarantees that intersection is empty
+
+    // cloning ctor
+    public Grammar(Grammar orig) {
+      this.rules = new Dictionary<char, List<string>>(orig.rules);
+      this.terminalSymbols = new HashSet<char>(orig.terminalSymbols);
+      this.sentenceSymbol = orig.sentenceSymbol;
+      this.nonTerminalSymbols = new HashSet<char>(orig.nonTerminalSymbols);
+      this.maxPhraseLength = new Dictionary<string, int>(orig.maxPhraseLength);
+      this.minPhraseLength = new Dictionary<string, int>(orig.minPhraseLength);
+    }
+
+    public Grammar(string grammar) : this((Grammar)FromString(grammar)) { }
+
+    public Grammar(char sentenceSymbol, IEnumerable<char> terminalSymbols, IEnumerable<char> nonTerminalSymbols, IEnumerable<Tuple<char, string>> rules) {
+      this.sentenceSymbol = sentenceSymbol;
+      this.terminalSymbols = new HashSet<char>(terminalSymbols);
+      this.nonTerminalSymbols = new HashSet<char>(nonTerminalSymbols);
+      this.rules = new Dictionary<char, List<string>>();
+      foreach (var r in rules) {
+        if (!this.rules.ContainsKey(r.Item1)) this.rules.Add(r.Item1, new List<string>());
+        this.rules[r.Item1].Add(r.Item2); // here we store an array of symbols for a phase
+      }
+
+      CheckValidity();
+      CalculatePhaseLengthBounds();
+    }
+
+    private void CheckValidity() {
+      // check validity of parameters
+      if (!nonTerminalSymbols.Contains(sentenceSymbol) || // sentence symbol must be a non-terminal
+          nonTerminalSymbols.Any(c => c < 'A' || c > 'Z') || // nonterminal symbols \in 'A' .. 'Z'
+          terminalSymbols.Intersect(nonTerminalSymbols).Any() || // no overlap between non-terminals and terminal
+          rules.Keys.Intersect(nonTerminalSymbols).Count() < nonTerminalSymbols.Count ||
+          nonTerminalSymbols.Any(nt => !rules.ContainsKey(nt)) || // each nt must have at least one rule
+          rules.Values.Any(alternatives => !alternatives.Any()) || // no eps alternatives
+          rules.Any(rule => rule.Value.Any(alternative => alternative.Length == 1 && alternative[0] == rule.Key))
+        // no infinite direct recursions
+        ) {
+        throw new ArgumentException();
+      }
+    }
+
+    private void CalculatePhaseLengthBounds() {
+      minPhraseLength.Clear();
+      maxPhraseLength.Clear();
+      // cache phrase lengths
+      foreach (var nt in nonTerminalSymbols) {
+        var min = int.MaxValue;
+        var max = int.MinValue;
+        foreach (var alt in rules[nt].OrderBy(alt => alt.Length)) {
+          minPhraseLength[alt] = MinPhraseLength(alt);
+          maxPhraseLength[alt] = MaxPhraseLength(alt);
+
+          min = Math.Min(min, minPhraseLength[alt]);
+          max = Math.Max(max, maxPhraseLength[alt]);
+        }
+        minPhraseLength[nt.ToString()] = min;
+        maxPhraseLength[nt.ToString()] = max;
+      }
+    }
+
+
+    public IEnumerable<string> GetAlternatives(char nt) {
+      return rules[nt];
+    }
+
+    public IEnumerable<string> GetTerminalAlternatives(char nt) {
+      return GetAlternatives(nt).Where(alt => alt.All(IsTerminal));
+    }
+
+    public IEnumerable<string> GetNonTerminalAlternatives(char nt) {
+      return GetAlternatives(nt).Where(alt => alt.Any(IsNonTerminal));
+    }
+
+    // caches for this are build in construction of object
+    public int MinPhraseLength(string phrase) {
+      int l;
+      if (minPhraseLength.TryGetValue(phrase, out l)) return l;
+      l = 0;
+      minPhraseLength[phrase] = short.MaxValue; // mark
+
+      foreach (var symb in phrase) {
+        if (IsNonTerminal(symb)) {
+          l += MinSymbolLength(symb);
+        } else {
+          l++;
+        }
+      }
+
+      l = Math.Min(short.MaxValue, l); // maximal allowed value is short.MaxValue
+      minPhraseLength[phrase] = l; // update 
+      return l;
+    }
+
+    // caches for this are build in construction of object
+    public int MaxPhraseLength(string phrase) {
+      int l;
+      if (maxPhraseLength.TryGetValue(phrase, out l)) return l;
+      l = 0;
+      maxPhraseLength[phrase] = short.MaxValue; // mark
+
+      foreach (var symb in phrase) {
+        if (IsNonTerminal(symb)) {
+          l += MaxSymbolLength(symb);
+        } else {
+          l++;
+        }
+      }
+      l = Math.Min(short.MaxValue, l); // maximal allowed value is short.MaxValue
+      maxPhraseLength[phrase] = l; // update 
+      return l;
+    }
+
+    private int MinSymbolLength(char nt) {
+      if (IsTerminal(nt)) return 1;
+      else return Math.Min(short.MaxValue, rules[nt].Min(alt => MinPhraseLength(alt))); // maximal allowed value is short.MaxValue
+    }
+    private int MaxSymbolLength(char nt) {
+      if (IsTerminal(nt)) return 1;
+      else return Math.Min(short.MaxValue, rules[nt].Max(alt => MaxPhraseLength(alt))); // maximal allowed value is short.MaxValue
+    }
+
+    public string CompleteSentenceRandomly(Random random, string phrase, int maxLen) {
+      if (phrase.Length > maxLen) throw new ArgumentException();
+      if (MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
+      bool done = phrase.All(IsTerminal); // terminal phrase means we are done
+      while (!done) {
+        int ntIdx; char nt;
+        FindFirstNonTerminal(phrase, out nt, out ntIdx);
+
+        int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
+        Debug.Assert(maxLenOfReplacement > 0);
+
+        var alts = GetAlternatives(nt).Where(alt => MinPhraseLength(alt) <= maxLenOfReplacement);
+        Debug.Assert(alts.Any());
+
+        // replace nt with random alternative
+        var selectedAlt = alts.SelectRandom(random);
+        phrase = phrase.Remove(ntIdx, 1);
+        phrase = phrase.Insert(ntIdx, selectedAlt);
+
+        done = phrase.All(IsTerminal); // terminal phrase means we are done
+      }
+      return phrase;
+    }
+
+    private void FindFirstNonTerminal(string phrase, out char nt, out int ntIdx) {
+      ntIdx = 0;
+      while (ntIdx < phrase.Length && IsTerminal(phrase[ntIdx])) ntIdx++;
+      if (ntIdx >= phrase.Length) {
+        ntIdx = -1;
+        nt = '\0';
+      } else {
+        nt = phrase[ntIdx];
+      }
+    }
+
+    public bool IsTerminal(char symbol) {
+      return terminalSymbols.Contains(symbol);
+    }
+
+    public bool IsNonTerminal(char symbol) {
+      return nonTerminalSymbols.Contains(symbol);
+    }
+
+    private static readonly string symbRegex = @"(?<symb>[^\s\|\.])";
+    private static readonly string altRegex = @"(?<alt>[^\s\|\.]+)";
+    private static readonly string altListRegex = altRegex + @"(\s*\|\s*" + altRegex + @")*";
+    // private static readonly string terminalClassRegex = @"[^\s\|\.]\s*\.\.\s*[^\s\|\.]";
+    private static readonly string terminalClassRegex = symbRegex + @"\s*\.\.\s*" + symbRegex + @"\s*";
+
+    private static readonly Regex sentenceSymbRegex = new Regex(@"\s*G\(" + symbRegex + @"\):\s*$", RegexOptions.ExplicitCapture);
+    private static readonly Regex ruleRegex = new Regex(@"\s*" + symbRegex + @"\s*->\s*(" + altListRegex + "|" + terminalClassRegex + @")\s*$", RegexOptions.ExplicitCapture);
+
+
+    // supports only meta-symbol for alternatives (syntax of formal grammars)
+    // epsilon-alternatives are not supported
+    public static IGrammar FromString(string grammar) {
+      char sentenceSymbol;
+      var nonTerminals = new List<char>();
+      var terminals = new List<char>();
+      var rules = new List<Tuple<char, string>>();
+
+      using (var reader = new StringReader(grammar)) {
+        var line = reader.ReadLine();
+        while (string.IsNullOrWhiteSpace(line)) line = reader.ReadLine();
+        // first line contains "G(...):"
+        var match = sentenceSymbRegex.Match(line);
+        if (!match.Success) throw new ArgumentException();
+        sentenceSymbol = match.Groups["symb"].Value[0]; // only a single symbol is in the capture group
+
+        line = reader.ReadLine();
+        while (!string.IsNullOrWhiteSpace(line)) {
+          match = ruleRegex.Match(line);
+          if (match.Length != line.Length) throw new ArgumentException();
+          var nt = match.Groups["symb"].Captures[0].Value[0];
+          if (!nonTerminals.Contains(nt)) nonTerminals.Add(nt);
+
+          // contains alternatives?
+          if (match.Groups["alt"].Captures.Count > 0) {
+            foreach (var m in match.Groups["alt"].Captures) {
+              rules.Add(Tuple.Create(nt, m.ToString()));
+            }
+          } else if (match.Groups["symb"].Captures.Count == 3) {
+            // contains terminal range
+            var fromSymb = match.Groups["symb"].Captures[1].Value[0];
+            var toSymb = match.Groups["symb"].Captures[2].Value[0];
+            if (fromSymb > toSymb) throw new ArgumentException("left symbol is larger than right symbol in range");
+
+            for (byte b = Convert.ToByte(fromSymb); b <= Convert.ToByte(toSymb); b++) {
+              rules.Add(Tuple.Create(nt, Convert.ToChar(b).ToString()));
+            }
+          }
+
+          line = reader.ReadLine();
+        }
+      }
+
+      foreach (var r in rules) {
+        foreach (var s in r.Item2) {
+          if (!nonTerminals.Contains(s) && !terminals.Contains(s)) terminals.Add(s);
+        }
+      }
+      return new Grammar(sentenceSymbol, terminals, nonTerminals, rules);
+    }
+
+    public override string ToString() {
+      // for debugging
+      var sb = new StringBuilder();
+      sb.AppendFormat("G({0}):", sentenceSymbol).AppendLine();
+      foreach (var r in rules) {
+        foreach (var alt in r.Value) {
+          var phrase = string.Join(" ", alt);
+          sb.AppendFormat("  {0} -> {1} (min: {2}, max {3})", r.Key, phrase, MinPhraseLength(phrase), MaxPhraseLength(phrase))
+            .AppendLine();
+        }
+      }
+      return sb.ToString();
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HardPalindromeProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HardPalindromeProblem.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HardPalindromeProblem.cs	(revision 11659)
@@ -0,0 +1,42 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public class HardPalindromeProblem : IProblem {
+    // length of the longest palindrome in the sentence + number of different symbols occurring in the palindrome
+    private const string grammarString = @"
+G(S):
+S -> T | TS
+T -> a .. z
+";
+
+    private readonly IGrammar grammar;
+    public HardPalindromeProblem() {
+      this.grammar = new Grammar(grammarString);
+    }
+
+    public double GetBestKnownQuality(int maxLen) {
+      // the whole sentence is a palindrome + each symbol occurs only once or twice
+      // for odd total length the number of different characters can be larger than len/2 (aba)
+      // the second part is limited to 26 different characters
+      return maxLen + Math.Min(26, (maxLen + 1) / 2);
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      var palindrome = PalindromeProblem.LongestPalindromicSubstring(sentence);
+      var palindromeBytes = ASCIIEncoding.ASCII.GetBytes(palindrome);
+      var chrCount = new int[256];
+      foreach (var b in palindromeBytes) {
+        chrCount[b]++;
+      }
+      return palindrome.Length + chrCount.Count(c => c > 0);
+    }
+
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj	(revision 11659)
@@ -0,0 +1,69 @@
+﻿<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="4.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <Import Project="$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props" Condition="Exists('$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props')" />
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <ProjectGuid>{CB9DCCF6-667E-4A13-B82D-DBD6B45A045E}</ProjectGuid>
+    <OutputType>Library</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <RootNamespace>HeuristicLab.Problems.GrammaticalOptimization</RootNamespace>
+    <AssemblyName>HeuristicLab.Problems.GrammaticalOptimization</AssemblyName>
+    <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
+    <FileAlignment>512</FileAlignment>
+    <TargetFrameworkProfile />
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+    <DebugSymbols>true</DebugSymbols>
+    <DebugType>full</DebugType>
+    <Optimize>false</Optimize>
+    <OutputPath>bin\Debug\</OutputPath>
+    <DefineConstants>DEBUG;TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+    <Prefer32Bit>false</Prefer32Bit>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+    <OutputPath>bin\Release\</OutputPath>
+    <DefineConstants>TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+    <Prefer32Bit>false</Prefer32Bit>
+  </PropertyGroup>
+  <ItemGroup>
+    <Reference Include="System" />
+    <Reference Include="System.Core" />
+    <Reference Include="System.Xml.Linq" />
+    <Reference Include="System.Data.DataSetExtensions" />
+    <Reference Include="Microsoft.CSharp" />
+    <Reference Include="System.Data" />
+    <Reference Include="System.Xml" />
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="ExpressionInterpreter.cs" />
+    <Compile Include="Extensions.cs" />
+    <Compile Include="Grammar.cs" />
+    <Compile Include="EvenParityProblem.cs" />
+    <Compile Include="SymbolicRegressionPoly10Problem.cs" />
+    <Compile Include="SantaFeAntProblem.cs" />
+    <Compile Include="IProblem.cs" />
+    <Compile Include="HardPalindromeProblem.cs" />
+    <Compile Include="IGrammar.cs" />
+    <Compile Include="PalindromeProblem.cs" />
+    <Compile Include="RoyalPairProblem.cs" />
+    <Compile Include="RoyalSymbolProblem.cs" />
+    <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="RoyalRoadProblem.cs" />
+    <Compile Include="RoyalTreeProblem.cs" />
+  </ItemGroup>
+  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
+  <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 
+       Other similar extension points exist, see Microsoft.Common.targets.
+  <Target Name="BeforeBuild">
+  </Target>
+  <Target Name="AfterBuild">
+  </Target>
+  -->
+</Project>
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IGrammar.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IGrammar.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IGrammar.cs	(revision 11659)
@@ -0,0 +1,27 @@
+﻿using System;
+using System.Collections.Generic;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+
+  // symbols are characters, possible nonterminal symbols are : 'A'..'Z'
+  // phrases and sentences are strings
+  // each symbol is only on element in a string
+
+  public interface IGrammar {
+    char SentenceSymbol { get; }
+    IEnumerable<char> NonTerminalSymbols { get; }
+    IEnumerable<char> TerminalSymbols { get; }
+    IEnumerable<char> Symbols { get; }
+
+    IEnumerable<string> GetAlternatives(char nt);
+    IEnumerable<string> GetTerminalAlternatives(char nt);
+    IEnumerable<string> GetNonTerminalAlternatives(char nt);
+
+    int MinPhraseLength(string phrase);
+    int MaxPhraseLength(string phrase);
+    string CompleteSentenceRandomly(Random random, string phrase, int maxLen);
+
+    bool IsTerminal(char symbol);
+    bool IsNonTerminal(char symbol);
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs	(revision 11659)
@@ -0,0 +1,12 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public interface IProblem {
+    double GetBestKnownQuality(int maxLen);
+    IGrammar Grammar { get; }
+    double Evaluate(string sentence);
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/PalindromeProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/PalindromeProblem.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/PalindromeProblem.cs	(revision 11659)
@@ -0,0 +1,82 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public class PalindromeProblem : IProblem {
+    // length of the longest palindrome in the sentence
+    private const string grammarString = @"
+G(S):
+S -> T | TS
+T -> a .. z
+";
+
+    private readonly IGrammar grammar;
+    public PalindromeProblem() {
+      this.grammar = new Grammar(grammarString);
+    }
+
+    public double GetBestKnownQuality(int maxLen) {
+      // the whole sentence is a palindrome
+      return maxLen;
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      return LongestPalindromicSubstring(sentence).Length;
+    }
+
+
+    private static string Preprocess(string s) {
+      var t = new char[2 * s.Length + 3];
+      t[0] = '$';
+      t[t.Length - 2] = '#';
+      t[t.Length - 1] = '@';
+      for (int i = 0; i < s.Length; i++) {
+        t[2 * (i) + 1] = '#';
+        t[2 * i + 2] = s[i];
+      }
+
+      return new string(t);
+    }
+
+    public static string LongestPalindromicSubstring(string str) {
+      var tLen = 2 * str.Length + 3;
+      var p = new int[tLen];
+      var t = Preprocess(str);
+
+      var center = 0;
+      var right = 0;
+      for (int i = 1; i < t.Length - 1; i++) {
+        var mirror = 2 * center - i;
+        if (right > i) p[i] = Math.Min(right - i, p[mirror]);
+        while (t[i + (1 + p[i])] == t[i - (1 + p[i])]) {
+          p[i]++;
+        }
+        if (i + p[i] > right) {
+          center = i;
+          right = i + p[i];
+        }
+      }
+      var len = 0;
+      center = 0;
+      for (int i = 0; i < t.Length - 1; i++) {
+        if (p[i] > len) {
+          center = i;
+          len = p[i];
+        }
+      }
+
+      var start = (center - 1 - len) / 2;
+      var result = new StringBuilder();
+      for (int i = 0; i < len; i++) {
+        result.Append(str[start + i]);
+      }
+      return result.ToString();
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Properties/AssemblyInfo.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Properties/AssemblyInfo.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Properties/AssemblyInfo.cs	(revision 11659)
@@ -0,0 +1,36 @@
+﻿using System.Reflection;
+using System.Runtime.CompilerServices;
+using System.Runtime.InteropServices;
+
+// General Information about an assembly is controlled through the following 
+// set of attributes. Change these attribute values to modify the information
+// associated with an assembly.
+[assembly: AssemblyTitle("HeuristicLab.Problems.GrammaticalOptimization")]
+[assembly: AssemblyDescription("")]
+[assembly: AssemblyConfiguration("")]
+[assembly: AssemblyCompany("Microsoft")]
+[assembly: AssemblyProduct("HeuristicLab.Problems.GrammaticalOptimization")]
+[assembly: AssemblyCopyright("Copyright © Microsoft 2014")]
+[assembly: AssemblyTrademark("")]
+[assembly: AssemblyCulture("")]
+
+// Setting ComVisible to false makes the types in this assembly not visible 
+// to COM components.  If you need to access a type in this assembly from 
+// COM, set the ComVisible attribute to true on that type.
+[assembly: ComVisible(false)]
+
+// The following GUID is for the ID of the typelib if this project is exposed to COM
+[assembly: Guid("3610cf30-7829-4163-bac6-46718baf5e80")]
+
+// Version information for an assembly consists of the following four values:
+//
+//      Major Version
+//      Minor Version 
+//      Build Number
+//      Revision
+//
+// You can specify all the values or you can default the Build and Revision Numbers 
+// by using the '*' as shown below:
+// [assembly: AssemblyVersion("1.0.*")]
+[assembly: AssemblyVersion("1.0.0.0")]
+[assembly: AssemblyFileVersion("1.0.0.0")]
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPairProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPairProblem.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPairProblem.cs	(revision 11659)
@@ -0,0 +1,36 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Text.RegularExpressions;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  // counts the number of times a pair of symbols occurs in a sentence
+  public class RoyalPairProblem : IProblem {
+    private const string grammarString = @"
+G(S):
+S -> a | aS | b | bS
+";
+
+    private readonly IGrammar grammar;
+    public RoyalPairProblem() {
+      this.grammar = new Grammar(grammarString);
+    }
+
+    public double GetBestKnownQuality(int maxLen) {
+      return maxLen - 1;
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    private Regex regex = new Regex("(?=ab)|(?=ba)"); // count the number of "ab" and "ba" pairs
+    public double Evaluate(string sentence) {
+      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
+      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
+      return regex.Matches(sentence).Count;
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalRoadProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalRoadProblem.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalRoadProblem.cs	(revision 11659)
@@ -0,0 +1,33 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public class RoyalRoadProblem : IProblem {
+    // inspired by Mitchell, Forrest, Holland: "The Royal Road for Genetic Algorithms: Fitness Landscapes and GA Performance", 1992
+    private const string grammarString = @"
+G(S):
+S -> 1 | 0 | 1S | 0S
+";
+
+    private readonly IGrammar grammar;
+    public RoyalRoadProblem() {
+      this.grammar = new Grammar(grammarString);
+    }
+
+    public double GetBestKnownQuality(int maxLen) {
+      // for now only an upper bound is returned, ideally all fitness cases are predicted correctly
+      throw new NotImplementedException();
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      throw new NotImplementedException();
+    }
+
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalSymbolProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalSymbolProblem.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalSymbolProblem.cs	(revision 11659)
@@ -0,0 +1,36 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text.RegularExpressions;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  // counts the number of times a symbol occurs in a sentence
+  public class RoyalSymbolProblem : IProblem {
+    private const string grammarString = @"
+G(S):
+S -> a | aS | b | bS
+";
+    // Obj(s \in L(G(S))) = Anzahl "a"-Symbole in s
+
+    private readonly IGrammar grammar;
+    public RoyalSymbolProblem() {
+      this.grammar = new Grammar(grammarString);
+    }
+
+    public double GetBestKnownQuality(int maxLen) {
+      return maxLen;
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    private Regex regex = new Regex("a"); // count the number of "a"s
+    public double Evaluate(string sentence) {
+      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
+      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
+      return regex.Matches(sentence).Count;
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalTreeProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalTreeProblem.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalTreeProblem.cs	(revision 11659)
@@ -0,0 +1,33 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public class RoyalTreeProblem : IProblem {
+    // Punch: "How Effective Are Multiple Populations in Genetic Programming", 1998
+    private const string grammarString = @"
+G(S):
+S -> 0 
+";
+
+    private readonly IGrammar grammar;
+    public RoyalTreeProblem() {
+      this.grammar = new Grammar(grammarString);
+    }
+
+    public double GetBestKnownQuality(int maxLen) {
+      // for now only an upper bound is returned, ideally all fitness cases are predicted correctly
+      throw new NotImplementedException();
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      throw new NotImplementedException();
+    }
+
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SantaFeAntProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SantaFeAntProblem.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SantaFeAntProblem.cs	(revision 11659)
@@ -0,0 +1,204 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Runtime.Remoting.Messaging;
+using System.Text;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public class SantaFeAntProblem : IProblem {
+    private const string grammarString = @"
+G(A):
+A -> l | r | m | ?(A)(A) | AA | AAA
+";
+    // Ant -> left | right | move | if-food-ahead Ant Ant | Ant Ant | Ant Ant Ant
+
+
+    private readonly IGrammar grammar;
+
+    public SantaFeAntProblem() {
+      this.grammar = new Grammar(grammarString);
+    }
+
+    public double GetBestKnownQuality(int maxLen) {
+      // for now only an upper bound is returned, ideally all food pellets are discovered
+      return 89;
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      var ant = new Ant();
+      int p = 0;
+      Run(ant, sentence, ref p);
+      return ant.FoodEaten;
+    }
+
+    private void Run(Ant ant, string sentence, ref int p) {
+      while (!ant.Done()) {
+        if (p >= sentence.Length) p = 0; // restart
+        switch (sentence[p]) {
+          case 'r': {
+              ant.TurnRight();
+              p++;
+              break;
+            }
+          case 'l': {
+              ant.TurnLeft();
+              p++;
+              break;
+            }
+          case 'm': {
+              ant.Move();
+              p++;
+              break;
+            }
+          case '?': {
+              p++; // skip p
+              if (ant.IsFoodAhead()) {
+                if (sentence[p] != '(') throw new ArgumentException();
+                p++;
+                Run(ant, sentence, ref p);      // it cannot happen that we run over the the end of the sentence here
+                if (ant.Done()) return;
+                if (sentence[p] != '(') throw new ArgumentException();
+                p++;
+                Skip(sentence, ref p);
+              } else {
+                if (sentence[p] != '(') throw new ArgumentException();
+                p++;
+                Skip(sentence, ref p);
+                if (sentence[p] != '(') throw new ArgumentException();
+                p++;
+                Run(ant, sentence, ref p);    // it cannot happen that we run over the the end of the sentence here
+              }
+              break;
+            }
+          case ')': {
+              p++; // skip
+              return;     // caller must continue processing
+            }
+          default: {
+              throw new ArgumentException();
+            }
+        }
+      }
+    }
+
+    private void Skip(string sentence, ref int p) {
+      int openCount = 1;
+      while (openCount > 0) {
+        if (sentence[p] == '(') openCount++;
+        else if (sentence[p] == ')') openCount--;
+        p++;
+      }
+    }
+  }
+
+  public class Ant {
+    private const int maxSteps = 600;
+    public enum HeadingEnum { North, East, South, West };
+    public int FoodEaten { get; private set; }
+    private readonly char[][] world = new char[32][];
+    private int posX;
+    private int posY;
+    private int steps;
+    private HeadingEnum heading;
+
+    public Ant() {
+      world[00] = " ###                            ".ToCharArray();
+      world[01] = "   #                            ".ToCharArray();
+      world[02] = "   #                    .###..  ".ToCharArray();
+      world[03] = "   #                    #    #  ".ToCharArray();
+      world[04] = "   #                    #    #  ".ToCharArray();
+      world[05] = "   ####.#####       .##..    .  ".ToCharArray();
+      world[06] = "            #       .        #  ".ToCharArray();
+      world[07] = "            #       #        .  ".ToCharArray();
+      world[08] = "            #       #        .  ".ToCharArray();
+      world[09] = "            #       #        #  ".ToCharArray();
+      world[10] = "            .       #        .  ".ToCharArray();
+      world[11] = "            #       .        .  ".ToCharArray();
+      world[12] = "            #       .        #  ".ToCharArray();
+      world[13] = "            #       #        .  ".ToCharArray();
+      world[14] = "            #       #  ...###.  ".ToCharArray();
+      world[15] = "            .   .#...  #        ".ToCharArray();
+      world[16] = "            .   .      .        ".ToCharArray();
+      world[17] = "            #   .      .        ".ToCharArray();
+      world[18] = "            #   #      .#...    ".ToCharArray();
+      world[19] = "            #   #          #    ".ToCharArray();
+      world[20] = "            #   #          .    ".ToCharArray();
+      world[21] = "            #   #          .    ".ToCharArray();
+      world[22] = "            #   .      ...#.    ".ToCharArray();
+      world[23] = "            #   .      #        ".ToCharArray();
+      world[24] = " ..##..#####.   #               ".ToCharArray();
+      world[25] = " #              #               ".ToCharArray();
+      world[26] = " #              #               ".ToCharArray();
+      world[27] = " #     .#######..               ".ToCharArray();
+      world[28] = " #     #                        ".ToCharArray();
+      world[29] = " .     #                        ".ToCharArray();
+      world[30] = " .####..                        ".ToCharArray();
+      world[31] = "                                ".ToCharArray();
+
+      posX = 0;
+      posY = 0;
+      heading = HeadingEnum.East;
+      FoodEaten = 0;
+      steps = 0;
+    }
+
+    public bool Done() {
+      return steps > maxSteps;
+    }
+
+    public void TurnRight() {
+      if (steps <= maxSteps) {
+        steps++;
+        if (heading == HeadingEnum.West) heading = HeadingEnum.North;
+        else heading++;
+      }
+    }
+
+    public void TurnLeft() {
+      if (steps <= maxSteps) {
+        steps++;
+        if (heading == HeadingEnum.North) heading = HeadingEnum.West;
+        else heading--;
+      }
+    }
+
+    public void Move() {
+      if (steps <= maxSteps) {
+        steps++;
+        MoveInternal(ref posX, ref posY);
+        if (world[posY][posX] == '#') {
+          FoodEaten++;
+          world[posY][posX] = '.';
+        }
+      }
+    }
+
+    private void MoveInternal(ref int posX, ref int posY) {
+      switch (heading) {
+        case HeadingEnum.North:
+          posY = (posY + 31) % 32;
+          break;
+        case HeadingEnum.East:
+          posX = (posX + 1) % 32;
+          break;
+        case HeadingEnum.South:
+          posY = (posY + 1) % 32;
+          break;
+        case HeadingEnum.West:
+          posX = (posX + 31) % 32;
+          break;
+      }
+    }
+
+    public bool IsFoodAhead() {
+      int nextPosX = posX;
+      int nextPosY = posY;
+      MoveInternal(ref nextPosX, ref nextPosY);
+      return world[nextPosY][nextPosX] == '#';
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs	(revision 11659)
@@ -0,0 +1,85 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Security;
+using System.Security.AccessControl;
+using System.Text;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public class SymbolicRegressionPoly10Problem : IProblem {
+    // length of the longest palindrome in the sentence + number of different symbols occurring in the palindrome
+    private const string grammarString = @"
+G(E):
+E -> V | V+E | V-E | V*E | V/E | (E)
+V -> a .. j 
+";
+
+    private readonly IGrammar grammar;
+    private readonly ExpressionInterpreter interpreter;
+
+    private readonly int N;
+    private readonly double[][] x;
+    private readonly double[] y;
+
+    public SymbolicRegressionPoly10Problem() {
+      this.grammar = new Grammar(grammarString);
+      this.interpreter = new ExpressionInterpreter();
+
+      this.N = 500;
+      this.x = new double[N][];
+      this.y = new double[N];
+
+      GenerateData();
+    }
+
+    private void GenerateData() {
+      // generate data with fixed seed to make sure that data is always the same
+      var rand = new Random(31415);
+      for (int i = 0; i < N; i++) {
+        x[i] = new double[10];
+        for (int j = 0; j < 10; j++) {
+          x[i][j] = rand.NextDouble() * 2 - 1;
+        }
+        // poly-10 no noise
+        y[i] = x[i][0] * x[i][1] +
+               x[i][2] * x[i][3] +
+               x[i][4] * x[i][5] +
+               x[i][0] * x[i][6] * x[i][8] +
+               x[i][2] * x[i][5] * x[i][9];
+      }
+    }
+
+    public double GetBestKnownQuality(int maxLen) {
+      // for now only an upper bound is returned, ideally we have an R² of 1.0
+      // the optimal R² can only be reached for sentences of at least 23 symbols
+      return 1.0;
+    }
+
+    public IGrammar Grammar {
+      get { return grammar; }
+    }
+
+    public double Evaluate(string sentence) {
+      return RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i])).ToArray());
+    }
+
+    private double RSq(IEnumerable<double> xs, IEnumerable<double> ys) {
+      // two pass implementation, but we don't care
+      var meanX = xs.Average();
+      var meanY = ys.Average();
+
+      var s = 0.0;
+      var ssX = 0.0;
+      var ssY = 0.0;
+      foreach (var p in xs.Zip(ys, (x, y) => new { x, y })) {
+        s += (p.x - meanX) * (p.y - meanY);
+        ssX += Math.Pow(p.x - meanX, 2);
+        ssY += Math.Pow(p.y - meanY, 2);
+      }
+
+      if (s.IsAlmost(0)) return 0;
+      if (ssX.IsAlmost(0) || ssY.IsAlmost(0)) return 0;
+      return s * s / (ssX * ssY);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Main.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Main.csproj	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Main.csproj	(revision 11659)
@@ -0,0 +1,71 @@
+﻿<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="4.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <Import Project="$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props" Condition="Exists('$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props')" />
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <ProjectGuid>{524CBD70-6F99-46AF-AD00-A0BC9FD1175B}</ProjectGuid>
+    <OutputType>Exe</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <RootNamespace>Main</RootNamespace>
+    <AssemblyName>Main</AssemblyName>
+    <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
+    <FileAlignment>512</FileAlignment>
+    <TargetFrameworkProfile />
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+    <PlatformTarget>AnyCPU</PlatformTarget>
+    <DebugSymbols>true</DebugSymbols>
+    <DebugType>full</DebugType>
+    <Optimize>false</Optimize>
+    <OutputPath>bin\Debug\</OutputPath>
+    <DefineConstants>DEBUG;TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+    <Prefer32Bit>false</Prefer32Bit>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+    <PlatformTarget>AnyCPU</PlatformTarget>
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+    <OutputPath>bin\Release\</OutputPath>
+    <DefineConstants>TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+    <Prefer32Bit>false</Prefer32Bit>
+  </PropertyGroup>
+  <ItemGroup>
+    <Reference Include="System" />
+    <Reference Include="System.Core" />
+    <Reference Include="System.Xml.Linq" />
+    <Reference Include="System.Data.DataSetExtensions" />
+    <Reference Include="Microsoft.CSharp" />
+    <Reference Include="System.Data" />
+    <Reference Include="System.Xml" />
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="Program.cs" />
+    <Compile Include="Properties\AssemblyInfo.cs" />
+  </ItemGroup>
+  <ItemGroup>
+    <ProjectReference Include="..\HeuristicLab.Algorithms.GrammaticalOptimization\HeuristicLab.Algorithms.GrammaticalOptimization.csproj">
+      <Project>{eea07488-1a51-412a-a52c-53b754a628b3}</Project>
+      <Name>HeuristicLab.Algorithms.GrammaticalOptimization</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Problems.GrammaticalOptimization\HeuristicLab.Problems.GrammaticalOptimization.csproj">
+      <Project>{cb9dccf6-667e-4a13-b82d-dbd6b45a045e}</Project>
+      <Name>HeuristicLab.Problems.GrammaticalOptimization</Name>
+    </ProjectReference>
+  </ItemGroup>
+  <ItemGroup>
+    <None Include="app.config" />
+  </ItemGroup>
+  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
+  <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 
+       Other similar extension points exist, see Microsoft.Common.targets.
+  <Target Name="BeforeBuild">
+  </Target>
+  <Target Name="AfterBuild">
+  </Target>
+  -->
+</Project>
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 11659)
@@ -0,0 +1,46 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using HeuristicLab.Algorithms.GrammaticalOptimization;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace Main {
+  class Program {
+    static void Main(string[] args) {
+      int maxIterations = 100000;
+      int iterations = 0;
+      var sw = new Stopwatch();
+      double bestQuality = 0;
+      string bestSentence = "";
+
+      var rs = new RandomSearch(100);
+
+      rs.FoundNewBestSolution += (sentence, quality) => {
+        bestQuality = quality;
+        bestSentence = sentence;
+        Console.WriteLine("{0,10} {1,10:F5} {2,10:F5} {3}", iterations, bestQuality, quality, sentence);
+      };
+      rs.SolutionEvaluated += (sentence, quality) => {
+        iterations++;
+        if (iterations % 1000 == 0) {
+          Console.WriteLine("{0,10} {1,10:F5} {2,10:F5} {3}", iterations, bestQuality, quality, sentence);
+        }
+      };
+
+
+      sw.Start();
+
+      rs.Run(new SymbolicRegressionPoly10Problem(), maxIterations);
+
+      sw.Stop();
+
+      Console.WriteLine("{0,10} Best soultion: {1,10:F5} {2}", iterations, bestQuality, bestSentence);
+      Console.WriteLine("{0:F2} sec {1,10:F1} sols/sec {2,10:F1} ns/sol",
+        sw.Elapsed.TotalSeconds,
+        maxIterations / (double)sw.Elapsed.TotalSeconds,
+        (double)sw.ElapsedMilliseconds * 1000 / maxIterations);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Properties/AssemblyInfo.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Properties/AssemblyInfo.cs	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Properties/AssemblyInfo.cs	(revision 11659)
@@ -0,0 +1,36 @@
+﻿using System.Reflection;
+using System.Runtime.CompilerServices;
+using System.Runtime.InteropServices;
+
+// General Information about an assembly is controlled through the following 
+// set of attributes. Change these attribute values to modify the information
+// associated with an assembly.
+[assembly: AssemblyTitle("Main")]
+[assembly: AssemblyDescription("")]
+[assembly: AssemblyConfiguration("")]
+[assembly: AssemblyCompany("Microsoft")]
+[assembly: AssemblyProduct("Main")]
+[assembly: AssemblyCopyright("Copyright © Microsoft 2014")]
+[assembly: AssemblyTrademark("")]
+[assembly: AssemblyCulture("")]
+
+// Setting ComVisible to false makes the types in this assembly not visible 
+// to COM components.  If you need to access a type in this assembly from 
+// COM, set the ComVisible attribute to true on that type.
+[assembly: ComVisible(false)]
+
+// The following GUID is for the ID of the typelib if this project is exposed to COM
+[assembly: Guid("6c9d053b-ed5d-4285-868a-1b6ea7587812")]
+
+// Version information for an assembly consists of the following four values:
+//
+//      Major Version
+//      Minor Version 
+//      Build Number
+//      Revision
+//
+// You can specify all the values or you can default the Build and Revision Numbers 
+// by using the '*' as shown below:
+// [assembly: AssemblyVersion("1.0.*")]
+[assembly: AssemblyVersion("1.0.0.0")]
+[assembly: AssemblyFileVersion("1.0.0.0")]
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/app.config
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/app.config	(revision 11659)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/app.config	(revision 11659)
@@ -0,0 +1,3 @@
+<?xml version="1.0"?>
+<configuration>
+<startup><supportedRuntime version="v4.0" sku=".NETFramework,Version=v4.5"/></startup></configuration>
