Weighted grammars and automata with threshold interpretation

摘要

We discuss a particular type of weighted grammars and automata over the partially ordered group of additive real vectors R{sup}k, and its subgroups Z{sup}k and Q{sup}k, as well as over the partially ordered group of component-wise multiplicative vectors with positive rational components. Computational power of these devices is investigated in comparison with the computational power of valence grammars and blind multicounter automata. We show that all these families are either full principal semi-AFL or full semi-AFL. Finally, some decidability matters are discussed.