Free inductive K-semialgebras

We consider rational power series over an alphabet Σ with coefficients in a ordered commutative semiring K and characterize them as the free ordered semialgebras in various classes defined by the least pre-fixed point rule and its dual. The results are generalizations of Kozen’s axiomatization of regular languages.     

Semitopological semirings and pushdown automata

This paper deals with algebraic power series over a commutative semiringA. A characteristization result states that a power series is algebraic if and only if it is the behavior of a proper pushdown automaton.To achieve this result some topological concepts are needed to be able to solve linear equations over semirings.     

An algebraic characterization of some principal regulated rational cones

The aim of this paper is to deal with formal power series over a commutative semiring A. Generalizing Wechler's pushdown automata and pushdown transition matrices yields a characterization of the A-semi-algebraic power series in terms of acceptance by pushdown automata. Principal regulated rational cones generated by cone generators of a certain form are characterized by algebraic systems given in certain matrix form. This yields a characterization of some principal full semi-AFL's in terms of context-free grammars. As an application of the theory, the principal regulated rational cone of one-counter “languages” is considered.     

Block-stochastic matrices and associated finite-state languages

Summary Finite automata are considered whose transition matrix is blockstochastic. The block-stochastic structure defines an equivalence relation among states of the automata. The implications of this relation are investigated, especially with respect to the languages accepted in the states of the automata.

---

Zusammenfassung Es werden Endliche Automaten betrachtet, deren Übergangsmatrix block-stochastisch ist. Die block-stochastische Struktur definiert eine Äquivalenzbeziehung zwischen Zuständen des Automaten. Die Bedeutung und Auswirkung dieser Relation wird untersucht, und zwar insbesonders in Hinsicht auf die in den einzelnen Zuständen des Automaten angenommenen Sprachen.