Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Polynomially Ambiguous Probabilistic Automata on Restricted Languages   We consider the computability and complexity of decision questions for
Probabilistic Finite Automata (PFA) with sub-exponential ambiguity. We show
that the emptiness problem for strict and non-strict cut-points 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 freeness/injectivity problems for
polynomially ambiguous PFA and study the border of decidability and
tractability for various cases.

32
The categories of this paper are: atom-ph
35
The categories of this paper are: mtrl-th
15
The categories of this paper are: nucl-ex
30
The categories of this paper are: q-alg
23
The categories of this paper are: solv-int
0
The categories of this paper are: hep-ph
26
The categories of this paper are: bayes-an
6
The categories of this paper are: astro-ph
20
The categories of this paper are: acc-phys
24
The categories of this paper are: dg-ga
14
The categories of this paper are: math-ph
17
The categories of this paper are: q-fin
16
The categories of this paper are: stat
19
The categories of this paper are: eess
2
The categories of this paper are: math
3
The categories of this paper are: physics