zbMATH — the first resource for mathematics

A solution to the problem of (\(A\),\(B\))-invariance for series. (English) Zbl 1025.68050
Summary: The aim of this article is to study a standard problem of control theory, the (\(A,B\))-invariance problem, which amounts to computing a maximal element \(X\) subject to conditions of the form \(AX\leqslant X+B\) and \(X\leqslant K\). We give a solution to the problem in the framework of formal series over particular complete idempotent semirings. Over finite idempotent semirings, we show that, under the assumption that \(B\) and \(K\) are recognizable series, the maximal solution exists and is also recognizable. We obtain a similar result for the infinite tropical semiring, with additional hypothesis that the series \(A\) is a language, but the notion of recognizable series has to be extended to the weaker notion of pseudo-recognizable series.

68Q45 Formal languages and automata
Full Text: DOI
[1] Berstel, J.; Reutenauer, C., Rational series and their languages, (1988), Springer Berlin · Zbl 0668.68005
[2] Gunawardena, J., An introduction to idempotency, (), (Chapter 1). · Zbl 0898.16032
[3] Higman, G., Ordering by divisibility in abstract algebras, Proc. London math. soc., 2, 326-336, (1952) · Zbl 0047.03402
[4] Klimann, I., New types of automata to solve fixed point problems, Theoret. comput. sci., 259, 183-197, (2001) · Zbl 0973.68122
[5] Pin, J.-E., Syntactic semigroups, (), (Chapter 10).
[6] Pin, J.-E.; Sakarovitch, J., Une application de la représentation matricielle des transductions, Theoret. comput. sci., 35, 271-293, (1985) · Zbl 0563.68064
[7] Sakarovitch, J.; Simon, I., Subwords, (), (Chapter 6).
[8] Wonham, W.M., Linear multivariable control—A geometric approach, (1985), Springer Berlin · Zbl 0393.93024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.