The equivalence of finite valued transducers (on HDT0L languages) is decidable
type: Item
instance of: scholarly article
title: The equivalence of finite valued transducers (on HDT0L languages) is decidable
zbMATH Open document ID: 0621.68049
DOI: 10.1016/0304-3975(86)90134-9
author: Karel II Culik
author: Juhani Karhumäki
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: See the review of the preliminary version in Zbl 0618.68069.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4007743
zbMATH Keywords: generalization of the Ehrenfeucht Conjecture
zbMATH Keywords: normalized k-valued finite transducers
zbMATH Keywords: HDT0L language
zbMATH Keywords: test set
zbMATH Keywords: equivalence problem
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90134-9
OpenAlex ID: W4212777194
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: Test sets for finite substitutions
cites work: Q3859267
cites work: The equivalence problem for deterministic two-tape automata
cites work: Single-valued a-transducers
cites work: The decidability of equivalence for deterministic finite transducers
cites work: Some decidability results about regular and pushdown translations
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: 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: Test sets and checking words for homomorphism equivalence
cites work: Multitape one-way nonwriting automata
cites work: The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable
cites work: Two-way counter machines and finite-state transducers†
cites work: A note on finite-valued and finitely ambiguous transducers
cites work: The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
cites work: The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
cites work: 2DST mappings of languages and related problems
cites work: Complete problems for deterministic polynomial time
cites work: The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
cites work: Q3736916
cites work: Q4430309
cites work: Q5533191
cites work: On cancellation properties of languages which are supports of rational power series
cites work: Q4140407
cites work: Explicit test sets for iterated morphisms in free monoids and metabelian groups
cites work: Q4101446
description: scientific article; zbMATH DE number 4007743