Twoway Parikh Automata. Parikh automata extend automata with counters whose values can only be tested at the end of the computation, with respect to membership into a semilinear set. Parikh automata have found several applications, for instance in transducer theory, as they enjoy decidable emptiness problem. In this paper, we study twoway Parikh automata. We show that emptiness becomes undecidable in the nondeterministic case. However, it is PSpaceC when the number of visits to any input position is bounded and the semilinear set is given as an existential Presburger formula. We also give tight complexity bounds for the inclusion, equivalence and universality problems. Finally, we characterise precisely the complexity of those problems when the semilinear constraint is given by an arbitrary Presburger formula.

Polynomially Ambiguous Probabilistic Automata on Restricted Languages We consider the computability and complexity of decision questions for Probabilistic Finite Automata (PFA) with subexponential ambiguity. We show that the emptiness problem for strict and nonstrict cutpoints of polynomially ambiguous commutative PFA remains undecidable, implying that the problem is undecidable when inputs are from a letter monotonic language. We show that the problem remains undecidable over a binary input alphabet when the input word is over a bounded language, in the noncommutative case. In doing so, we introduce a new technique based upon the Turakainen construction of a PFA from a Weighted Finite Automata which can be used to generate PFA of lower dimensions and of subexponential ambiguity. We also study freenessinjectivity problems for polynomially ambiguous PFA and study the border of decidability and tractability for various cases.