Rational relations and rational series
type: Item
instance of: scholarly article
title: Rational relations and rational series
zbMATH Open document ID: 0777.68068
DOI: 10.1016/0304-3975(92)90375-P
author: Christian Choffrut
published in: Theoretical Computer Science
publication date: 1992-09-27T00:00:00Z
review text: The paper deals with noncommutative rational series over an alphabet \(A\) with multiplicities in subsemirings of Rat \(B^*\). It is especially devoted to Fatou extension problems and usual decidability questions (equivalence, intersection, finiteness) concerning such series. It is proved in particular that the intersection problem is undecidable for rational series over the semiring of finite subsets of a one-letter alphabet.
reviewed by: Daniel Krob
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 16Y60
zbMATH DE Number: 64223
zbMATH Keywords: rational relation
zbMATH Keywords: tropical semiring
zbMATH Keywords: decision problem
zbMATH Keywords: rational series
zbMATH Keywords: semiring
MaRDI profile type: Publication
cites work: Characterizations of the decidability of some problems for regular trace languages
cites work: Q3859267
cites work: Q3673137
cites work: Q3856952
cites work: Q4079524
cites work: Q4105059
cites work: On the decidability of some problems about rational subsets of free partially commutative monoids
cites work: Limitedness theorem on finite automata with distance functions
cites work: Reversal-Bounded Multicounter Machines and Their Decision Problems
cites work: La finitude des représentations linéaires des semi-groupes est decidable
cites work: On the definition of a family of automata
cites work: Q3804221
description: scientific article; zbMATH DE number 64223