Equations over finite sets of words and equivalence problems in automata theory
type: Item
instance of: scholarly article
title: Equations over finite sets of words and equivalence problems in automata theory
zbMATH Open document ID: 0787.20035
DOI: 10.1016/0304-3975(93)90232-I
author: Juhani Karhumäki
published in: Theoretical Computer Science
publication date: 1993-10-17T00:00:00Z
review text: Equations over the monoid \(FS\) of finite sets of words are studied here. In particular, it is shown that a constant-free equation \(u = v\) has a nontrivial solution in the monoid \(FS\) if and only if the equation has a nontrivial solution in the free monoid of finite words. The Ehrenfeucht conjecture is proved to hold for the (free) monoid of prefix codes: Each system of equations in a finite number of variables is equivalent to a finite subsystem. A restriction of this statement is proved for the monoid of finite multisets (or polynomials) of words. The paper contains also applications to automata theory and a list of open problems.
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 08A40
zbMATH DE Number: 417373
zbMATH Keywords: finite sets of words
zbMATH Keywords: free monoid
zbMATH Keywords: Ehrenfeucht conjecture
zbMATH Keywords: monoid of prefix codes
zbMATH Keywords: system of equations
zbMATH Keywords: finite subsystem
zbMATH Keywords: monoid of finite multisets
reviewed by: Tero Harju
MaRDI profile type: Publication
cites work: Test sets for context free languages and algebraic systems of equations over a free monoid
cites work: A proof of Ehrenfeucht's conjecture
cites work: Centralizers in Free Associative Algebras
cites work: Q3859267
cites work: Q4430300
cites work: Q3994777
cites work: Free Associative Algebras
cites work: Q3808246
cites work: The decidability of the equivalence problem for DOL-systems
cites work: Systems of equations over a free monoid and Ehrenfeucht's conjecture
cites work: Q3711770
cites work: The equivalence of finite valued transducers (on HDT0L languages) is decidable
cites work: The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable
cites work: On the decidability of homomorphism equivalence for languages
cites work: Q4079524
cites work: The equivalence problem of multitape finite automata
cites work: Equations in free semigroups
cites work: The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
cites work: Q3782812
cites work: Q3769982
cites work: Q4430309
cites work: Q3659988
cites work: THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
cites work: Codes conjugués
cites work: Codes et motifs
cites work: Q4140407
cites work: Q5678435
cites work: Sur les rélations rationnelles entre monoides libres
cites work: Q4001349
description: scientific article; zbMATH DE number 417373