  It is well known that the problem solving equations in virtually free groups
can be reduced to the problem of solving twisted word equations with regular
constraints over free monoids with involution. In this paper we prove that the
set of all solutions of a twisted word equation is an EDT0L language whose
specification can be computed in $\mathsf{PSPACE}$. Within the same complexity
bound we can decide whether the solution set is empty, finite, or infinite.
  In the second part of the paper we apply the results for twisted equations to
obtain in $\mathsf{PSPACE}$ an EDT0L description of the solution set of
equations with rational constraints for finitely generated virtually free
groups in standard normal forms with respect to a natural set of generators. If
the rational constraints are given by a homomorphism into a fixed (or "small
enough") finite monoid, then our algorithms can be implemented in
$\mathsf{NSPACE}(n^2\log n)$, that is, in quasi-quadratic nondeterministic
space.
  Our results generalize the work by Lohrey and S\'enizergues (ICALP 2006) and
Dahmani and Guirardel (J. of Topology 2010) with respect to both complexity and
expressive power. Neither paper gave any concrete complexity bound and the
results in these papers are stated for subsets of solutions only, whereas our
results concern all solutions.

Group Theory;Computational Complexity;Formal Languages and Automata Theory;Logic in Computer Science