| Abstrakt: | We explore fundamental properties of several variants of structurally restricted weighted automata with emphasis on the case of automata over tropical semirings. We also study hardness of decision problems, considered by S. Almagor, U. Boker, and O. Kupferman for general weighted automata over tropical semirings, in the following restricted settings. We define branchless automata as a subclass of acyclic automata with loops. For branchless automata over tropical semiring of natural numbers we show that the upper boundedness problem and the absolute boundedness problem belong to P, the universality problem and the forall-exact problem belong to co-NP, and the exists-exact problem is NP-hard. For acyclic weighted automata with loops, we observe that all decision problems that are decidable in the general setting, do not become easier.
|
|---|