Rational equivalence relations
type: Item
instance of: scholarly article
title: Rational equivalence relations
zbMATH Open document ID: 0619.68051
DOI: 10.1016/0304-3975(86)90132-5
author: J. Howard Johnson
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: Rational relations (finite transductions) which are equivalence relations are discussed. After establishing a containment hierarchy, the complexity of canonical function computation and a number of class membership decision problems are studied. The following classes are considered: (1) rational equivalence relations, (2) equivalence kernels of rational functions, (3) deterministic rational equivalence relations, (4) equivalence kernels of subsequential functions, (5) recognizable equivalence relations, (6) length-bounded rational equivalence relations, and (7) finite equivalence relations. Except for one open case ((1)\(=^{?}(2))\), Hasse diagrams are given to show the relative containments in the general and one-letter-alphabet cases. Canonical function application for an input of length n is shown to be \(O(n^ 2)\) time and space for (1), O(n) time and space for (2), (3), and (6), and O(n) time and constant space for the others. It is shown that transitivity, symmetry, reflexitivity, and membership in any of (1) through (5) are undecidable properties for rational relations whereas membership in (6) or (7) is decidable.
Mathematics Subject Classification ID: 68Q99
Mathematics Subject Classification ID: 68T99
zbMATH DE Number: 4005623
zbMATH Keywords: finite transductions
zbMATH Keywords: containment hierarchy
zbMATH Keywords: complexity of canonical function computation
zbMATH Keywords: class membership decision problems
zbMATH Keywords: rational equivalence relations
zbMATH Keywords: equivalence kernels of rational functions
zbMATH Keywords: equivalence kernels of subsequential functions
zbMATH Keywords: recognizable equivalence relations
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90132-5
OpenAlex ID: W3102069426
cites work: Q3859267
cites work: The equivalence problem for deterministic two-tape automata
cites work: Single-valued a-transducers
cites work: Une caractérisation des fonctions séquentielles et des fonctions sous- séquentielles en tant que rélations rationnelles
cites work: Q4079524
cites work: On Relations Defined by Generalized Finite Automata
cites work: Q5580840
cites work: Multitape one-way nonwriting automata
cites work: Q5576254
cites work: Q3687745
cites work: Q4057549
cites work: A faster algorithm computing string edit distances
cites work: Transductions des langages de Chomsky
cites work: A remark on finite transducers
cites work: Sur certains sous-monoïdes libres
cites work: Efficient recognition of rational relations
cites work: Q3962496
description: scientific article; zbMATH DE number 4005623