Decision problems concerning algebraic series with noncommuting variables

DOI10.1007/3-540-63246-8_17MaRDI QIDQ4362736zbMATH OpenFDO

Authors Juha Honkala

Publication date 14 December 1997

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-63246-8_17

zbMATH Keywords

algebraic seriesequivalence problemnoncommuting variablesrationality problem

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Word problems, etc. in computability and recursion theory (03D40) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Review text

It is shown that the equivalence and the rationality problem are decidable for algebraic series with noncommuting variables having bounded supports. The proofs use Parikh simplifying mapping. For the entire collection see [Zbl 0868.00014].

Cited in

(3)

• Some decision problems concerning semilinearity and commutation.
• Language equivalence of probabilistic pushdown automata
• Sparse and slender subsets of monoids.

This page was built for publication: Decision problems concerning algebraic series with noncommuting variables

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