Index: /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/FirstOrderMarkovModel.java
===================================================================
--- /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/FirstOrderMarkovModel.java	(revision 257)
+++ /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/FirstOrderMarkovModel.java	(revision 258)
@@ -3,4 +3,5 @@
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.LinkedList;
 import java.util.List;
 import java.util.Random;
@@ -99,15 +100,29 @@
 		int numStates = knownSymbols.size();
 
-		int startStateIndex = knownSymbols.indexOf(Event.STARTEVENT);
-		int endStateIndex = knownSymbols.indexOf(Event.ENDEVENT);
-		if (startStateIndex == -1) {
+		List<Integer> startIndexList = new LinkedList<Integer>();
+		List<Integer> endIndexList = new LinkedList<Integer>();
+		for( int i=0 ; i<knownSymbols.size() ; i++ ) {
+			String id = knownSymbols.get(i).getStandardId();
+			if( id.equals(Event.STARTEVENT.getStandardId()) || id.contains(Event.STARTEVENT.getStandardId()+"-=-") ) {
+				startIndexList.add(i);
+			}
+			if( id.equals(Event.ENDEVENT.getStandardId()) || id.contains("-=-"+Event.ENDEVENT.getStandardId()) ) {
+				endIndexList.add(i);
+			}
+		}
+		
+		if (startIndexList.isEmpty()) {	
 			Console.printerrln("Error calculating entropy. Initial state of markov chain not found.");
 			return Double.NaN;
 		}
-		if (endStateIndex == -1) {
+		if (endIndexList.isEmpty()) {
 			Console.printerrln("Error calculating entropy. End state of markov chain not found.");
 			return Double.NaN;
 		}
-		transmissionMatrix.set(endStateIndex, startStateIndex, 1);
+		for( Integer i : endIndexList ) {
+			for(Integer j : startIndexList ) {
+				transmissionMatrix.set(i, j, 1);
+			}
+		}
 
 		// Calculate stationary distribution by raising the power of the
@@ -160,5 +175,4 @@
 		List<Event<?>> knownSymbols = new ArrayList<Event<?>>(
 				trie.getKnownSymbols());
-
 		for (Event<?> symbol : knownSymbols) {
 			final String thisSaneId = symbol.getShortId().replace("\"", "\\\"")
@@ -183,5 +197,5 @@
 	/**
 	 * <p>
-	 * Returns a {@link Graph} represenation of the model with the states as
+	 * Returns a {@link Graph} representation of the model with the states as
 	 * nodes and directed edges weighted with transition probabilities.
 	 * </p>
Index: /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/ModelFlattener.java
===================================================================
--- /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/ModelFlattener.java	(revision 258)
+++ /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/ModelFlattener.java	(revision 258)
@@ -0,0 +1,137 @@
+package de.ugoe.cs.eventbench.models;
+
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+import de.ugoe.cs.eventbench.data.Event;
+import de.ugoe.cs.eventbench.data.ReplayableEvent;
+
+/**
+ * <p>
+ * This class provides functions to create flattened first-order Markov models
+ * from {@link HighOrderMarkovModel}s and {@link PredictionByPartialMatch}
+ * models through state splitting.
+ * </p>
+ * <p>
+ * If possible, the normal high-order markov model should be used, as the Events
+ * may be broken by the flattener, as, e.g., the information
+ * {@link ReplayableEvent}s contain is not preserved.
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class ModelFlattener {
+
+	private static final String EVENT_SEPARATOR = "-=-";
+
+	Trie<Event<?>> firstOrderTrie;
+
+	/**
+	 * <p>
+	 * Takes a {@link HighOrderMarkovModel} and returns a
+	 * {@link FirstOrderMarkovModel} that conserves the high-order memory
+	 * through state splitting.
+	 * </p>
+	 * 
+	 * @param model
+	 *            model that is flattened
+	 * @return flattened first-order Markov model
+	 */
+	public FirstOrderMarkovModel flattenHighOrderMarkovModel(
+			HighOrderMarkovModel model) {
+		int markovOrder = model.trieOrder - 1;
+		if (markovOrder == 1) {
+			// TODO model is already FOM
+			// requires copy constructor in class trie
+		}
+		firstOrderTrie = new Trie<Event<?>>();
+		TrieNode<Event<?>> rootNode = model.trie.find(null);
+		generateFirstOrderTrie(rootNode, new LinkedList<String>(), markovOrder);
+		firstOrderTrie.updateKnownSymbols();
+
+		FirstOrderMarkovModel firstOrderModel = new FirstOrderMarkovModel(
+				new Random());
+		firstOrderModel.trie = firstOrderTrie;
+		firstOrderModel.trieOrder = 2;
+
+		return firstOrderModel;
+	}
+
+	/**
+	 * <p>
+	 * <b>This method is not available yet and always return null!</b>
+	 * </p>
+	 * <p>
+	 * Takes a {@link PredictionByPartialMatch} model and returns a
+	 * {@link FirstOrderMarkovModel} that conserves the high-order memory
+	 * through state splitting.
+	 * </p>
+	 * 
+	 * @param model
+	 *            model that is flattened
+	 * @return flattened first-order Markov model
+	 */
+	public FirstOrderMarkovModel flattenPredictionByPartialMatch(
+			PredictionByPartialMatch model) {
+		// TODO implement method
+		return null;
+	}
+
+	/**
+	 * <p>
+	 * Converts all nodes of the given depth into first-order node through
+	 * state-splitting. For each node at the given depth a new node is created
+	 * and appropriate transitions will be added.
+	 * </p>
+	 * <p>
+	 * This method traverses through the tree recursively. If the recursion
+	 * reaches the desired depth in the tree, node are added.
+	 * </p>
+	 * 
+	 * @param currentNode
+	 *            node whose sub-trie is currently traversed
+	 * @param parentIDs
+	 *            ID strings of the ancestors of the currentNode
+	 * @param depth
+	 *            depth to go - NOT the current depth.
+	 */
+	private void generateFirstOrderTrie(TrieNode<Event<?>> currentNode,
+			List<String> parentIDs, int depth) {
+		for (TrieNode<Event<?>> child : currentNode.getChildren()) {
+			String currentId = child.getSymbol().getStandardId();
+			if (depth > 1) {
+				List<String> childParentIDs = new LinkedList<String>(parentIDs);
+				childParentIDs.add(currentId);
+				generateFirstOrderTrie(child, childParentIDs, depth - 1);
+
+			} else {
+				StringBuilder firstOrderID = new StringBuilder();
+				for (String parentID : parentIDs) {
+					firstOrderID.append(parentID + EVENT_SEPARATOR);
+				}
+				firstOrderID.append(currentId);
+				TrieNode<Event<?>> firstOrderNode = firstOrderTrie
+						.getChildCreate(new Event<Object>(firstOrderID
+								.toString()));
+				firstOrderNode.setCount(child.getCount());
+				for (TrieNode<Event<?>> transitionChild : child.getChildren()) {
+					StringBuilder transitionID = new StringBuilder();
+					for (String parentID : parentIDs.subList(1,
+							parentIDs.size())) {
+						transitionID.append(parentID + EVENT_SEPARATOR);
+					}
+					transitionID.append(currentId + EVENT_SEPARATOR);
+					transitionID.append(transitionChild.getSymbol()
+							.getStandardId());
+					TrieNode<Event<?>> firstOrderTransitionChild = firstOrderNode
+							.getChildCreate(new Event<Object>(transitionID
+									.toString()));
+					firstOrderTransitionChild.setCount(transitionChild
+							.getCount());
+				}
+			}
+		}
+	}
+}
Index: /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/PredictionByPartialMatch.java
===================================================================
--- /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/PredictionByPartialMatch.java	(revision 257)
+++ /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/PredictionByPartialMatch.java	(revision 258)
@@ -34,5 +34,5 @@
 	 * </p>
 	 */
-	private int minOrder;
+	protected int minOrder;
 
 	/**
@@ -41,5 +41,5 @@
 	 * </p>
 	 */
-	double probEscape;
+	protected double probEscape;
 
 	/**
Index: /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/Trie.java
===================================================================
--- /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/Trie.java	(revision 257)
+++ /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/Trie.java	(revision 258)
@@ -85,5 +85,5 @@
 	 */
 	public void train(List<T> sequence, int maxOrder) {
-		if( maxOrder<1 ) {
+		if (maxOrder < 1) {
 			return;
 		}
@@ -400,3 +400,17 @@
 		return rootNode.getNumLeafs();
 	}
+
+	/**
+	 * <p>
+	 * Updates the list of known symbols by replacing it with all symbols that
+	 * are found in the child nodes of the root node. This should be the same as
+	 * all symbols that are contained in the trie.
+	 * </p>
+	 */
+	public void updateKnownSymbols() {
+		knownSymbols = new HashSet<T>();
+		for (TrieNode<T> node : rootNode.getChildren()) {
+			knownSymbols.add(node.getSymbol());
+		}
+	}
 }
Index: /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieNode.java
===================================================================
--- /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieNode.java	(revision 257)
+++ /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieNode.java	(revision 258)
@@ -178,4 +178,15 @@
 	/**
 	 * <p>
+	 * Returns all children of this node.
+	 * </p>
+	 * 
+	 * @return children of this node
+	 */
+	protected Collection<TrieNode<T>> getChildren() {
+		return children;
+	}
+
+	/**
+	 * <p>
 	 * Searches the sub-trie of this trie node for a given sequence and returns
 	 * the node associated with the sequence or null if no such node is found.
@@ -298,5 +309,5 @@
 		return children.isEmpty();
 	}
-	
+
 	/**
 	 * <p>
@@ -307,5 +318,5 @@
 	 */
 	protected boolean isRoot() {
-		return symbol==null;
+		return symbol == null;
 	}
 
@@ -329,14 +340,18 @@
 		}
 	}
-	
-	/**
-	 * <p>Returns the number of descendants of this node that are leafs. This does not only include direct children of this node, but all leafs in the sub-trie with this node as root.
-	 * </p>
-	 * @return
+
+	/**
+	 * <p>
+	 * Returns the number of descendants of this node that are leafs. This does
+	 * not only include direct children of this node, but all leafs in the
+	 * sub-trie with this node as root.
+	 * </p>
+	 * 
+	 * @return number of leafs in this sub-trie
 	 */
 	protected int getNumLeafs() {
 		int numLeafs = 0;
-		for( TrieNode<T> child : children) {
-			if( child.isLeaf() ) {
+		for (TrieNode<T> child : children) {
+			if (child.isLeaf()) {
 				numLeafs++;
 			} else {
@@ -346,3 +361,19 @@
 		return numLeafs;
 	}
+
+	/**
+	 * <p>
+	 * Sets the {@link #count} of this node.
+	 * </p>
+	 * <p>
+	 * This function should only be used sparingly and very carefully! The count
+	 * is usually maintained automatically by the training procedures.
+	 * </p>
+	 * 
+	 * @param count
+	 *            new count
+	 */
+	protected void setCount(int count) {
+		this.count = count;
+	}
 }