Descriptional complexity of automata and grammars
state-complexity of finite automata, algorithms for automata operations and implementation
nondeterminism measures for (pushdown) automata, complexity of parsing
synchronization expressions for parallel processes; fairness and trajectories
tree automata and term rewriting systems: modularity and decidability