Automata and languages generalized to -continuous semirings

DOI10.1016/0304-3975(91)90147-TMaRDI QIDQ2640344zbMATH OpenFDO

Authors W. Kuich

Publication date 1991

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(91)90147-T

zbMATH Keywords

\(\omega \) -continuous semiringKleene's theorempolynomial algebrapushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Review text

After presenting some basic notions and results about \(\omega\)-finitary semirings, one defines automata over \(\omega\)-continuous semirings and a generalization of the Kleene Theorem to this case is proved. (The result has been reported in \textit{W. Kuich} [Lect. Notes Comput. Sci. 267, 212- 225 (1987; Zbl 0625.16026)], the Kleene and the Parikh Theorems in complete semirings. Algebraic systems in the polynomial algebra over an \(\omega\)-continuous semiring and pushdown automata over \(\omega\)-continuous semirings are defined and shown to be equivalent, thus generalizing a known characterization of context-free languages.

Recommendations

• scientific article; zbMATH DE number 177807
• ^*-continuous Kleene -algebras
• Theory Is Forever
• A Kleene theorem for weighted -pushdown automata
• Forty years of formal power series in automata theory

Cited in

(32)

• A note on: `Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages' (by K. Ayers)
• Accepting conditions for automata on -languages
• On transductions of formal power series over complete semirings
• On limits in complete semirings
• On Lindenmayerian algebraic power series
• On Lindenmayerian algebraic sequences
• The equational logic of fixed points
• On D0L power series
• The validity of weighted automata
• Unique, guarded fixed points in an additive setting: extended abstract
• On the generative power of -grammars and -automata
• On syntactic nuclei of rational languages
• scientific article; zbMATH DE number 4178794 (Why is no real title available?)
• scientific article; zbMATH DE number 5155118 (Why is no real title available?)
• ^*-continuous Kleene -algebras
• A semiring-semimodule generalization of transducers and abstract \(\omega\)-families of power series
• scientific article; zbMATH DE number 3930367 (Why is no real title available?)
• scientific article; zbMATH DE number 3988721 (Why is no real title available?)
• Semitopological semirings and pushdown automata
• scientific article; zbMATH DE number 177807 (Why is no real title available?)
• scientific article; zbMATH DE number 1944130 (Why is no real title available?)
• The algebraic equivalent of AFL theory
• Mathematical Foundations of Computer Science 2004
• scientific article; zbMATH DE number 6764298 (Why is no real title available?)
• A Kleene theorem for weighted -pushdown automata
• Continuous semiring-semimodule pairs and mixed algebraic systems
• scientific article; zbMATH DE number 7649888 (Why is no real title available?)
• Theory Is Forever
• The net automaton of a rational expression
• An iteration property of Lindenmayerian power series
• Representations and complete semiring morphisms
• r -invertible matrices over commutative semirings

This page was built for publication: Automata and languages generalized to \(\omega\)-continuous semirings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2640344)