Eulerian Paths with Regular Constraints ======================================= Labeled graphs, in which edges are labeled by letters from some alphabet $\Sigma$, are extensively used to model many types of relations associated with actions, costs, owners, or other properties. Each path in a labeled graph induces a word in $\Sigma^*$ -- the one obtained by concatenating the letters along the edges in the path. Classical graph-theory problems give rise to new problems that take these words into account. We introduce and study the {\em constrained Eulerian path\/} problem. The input to the problem is a $\Sigma$-labeled graph $G$ and a specification $L \subseteq \Sigma^*$. The goal is to find an Eulerian path in $G$ that satisfies $L$. We consider several classes of the problem, defined by the classes of $G$ and $L$. We focus on the case $L$ is regular and show that while the problem is in general NP-complete, even for very simple graphs and specifications, there are classes that can be solved efficiently. Our results extend work on Eulerian paths with edge-order constraints. We also study the {\em constrained Chinese postman\/} problem, where edges have costs and the goal is to find a cheapest path that contains each edge at least once and satisfies the specification. Finally, we define and study the {\em Eulerian language\/} of a graph, namely the set of words along its Eulerian paths.