Equivalence of finite-valued bottom-up finite state tree transducers is decidable

Helmut Seidl

doi:10.1007/3-540-52590-4_54

Equivalence of finite-valued bottom-up finite state tree transducers is decidable

Helmut Seidl

Saarland University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

6 Scopus citations

Abstract

A bottom-up finite state tree transducer (FST) A is called k-valued iff for every input tree there are at most k different output trees. A is called finite-valued iff it is k-valued for some k. We show: it is decidable for every k whether or not a given FST A is k-valued, and it is decidable whether or not A is finite-valued. We give an effective characterization of all finite-valued FST's and derive a (sharp) upper bound for the valuedness provided it is finite. We decompose a finite-valued FST A into a finite number of single-valued FST's. This enables us to prove: it is decidable whether or not the translation of an FST A is included in the translation of a finite-valued FST A’.

Original language	English
Title of host publication	CAAP 1990 - 15th Colloquium on Trees in Algebra and Programming, Proceedings
Editors	Andre Arnold
Publisher	Springer Verlag
Pages	269-284
Number of pages	16
ISBN (Print)	9783540525905
DOIs	https://doi.org/10.1007/3-540-52590-4_54
State	Published - 1990
Externally published	Yes
Event	15th Colloquium on Trees in Algebra and Programming, CAAP 1990 - Copenhagen, Denmark Duration: 15 May 1990 → 18 May 1990

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	431 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	15th Colloquium on Trees in Algebra and Programming, CAAP 1990
Country/Territory	Denmark
City	Copenhagen
Period	15/05/90 → 18/05/90

Access to Document

10.1007/3-540-52590-4_54

Cite this

Seidl, H. (1990). Equivalence of finite-valued bottom-up finite state tree transducers is decidable. In A. Arnold (Ed.), CAAP 1990 - 15th Colloquium on Trees in Algebra and Programming, Proceedings (pp. 269-284). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 431 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-52590-4_54

Seidl, Helmut. / Equivalence of finite-valued bottom-up finite state tree transducers is decidable. CAAP 1990 - 15th Colloquium on Trees in Algebra and Programming, Proceedings. editor / Andre Arnold. Springer Verlag, 1990. pp. 269-284 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{efbf1322ff824d9dbf6c72e5b0d3402a,

title = "Equivalence of finite-valued bottom-up finite state tree transducers is decidable",

abstract = "A bottom-up finite state tree transducer (FST) A is called k-valued iff for every input tree there are at most k different output trees. A is called finite-valued iff it is k-valued for some k. We show: it is decidable for every k whether or not a given FST A is k-valued, and it is decidable whether or not A is finite-valued. We give an effective characterization of all finite-valued FST's and derive a (sharp) upper bound for the valuedness provided it is finite. We decompose a finite-valued FST A into a finite number of single-valued FST's. This enables us to prove: it is decidable whether or not the translation of an FST A is included in the translation of a finite-valued FST A{\textquoteright}.",

author = "Helmut Seidl",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1990.; 15th Colloquium on Trees in Algebra and Programming, CAAP 1990 ; Conference date: 15-05-1990 Through 18-05-1990",

year = "1990",

doi = "10.1007/3-540-52590-4_54",

language = "English",

isbn = "9783540525905",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "269--284",

editor = "Andre Arnold",

booktitle = "CAAP 1990 - 15th Colloquium on Trees in Algebra and Programming, Proceedings",

}

Seidl, H 1990, Equivalence of finite-valued bottom-up finite state tree transducers is decidable. in A Arnold (ed.), CAAP 1990 - 15th Colloquium on Trees in Algebra and Programming, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 431 LNCS, Springer Verlag, pp. 269-284, 15th Colloquium on Trees in Algebra and Programming, CAAP 1990, Copenhagen, Denmark, 15/05/90. https://doi.org/10.1007/3-540-52590-4_54

Equivalence of finite-valued bottom-up finite state tree transducers is decidable. / Seidl, Helmut.
CAAP 1990 - 15th Colloquium on Trees in Algebra and Programming, Proceedings. ed. / Andre Arnold. Springer Verlag, 1990. p. 269-284 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 431 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Equivalence of finite-valued bottom-up finite state tree transducers is decidable

AU - Seidl, Helmut

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1990.

PY - 1990

Y1 - 1990

N2 - A bottom-up finite state tree transducer (FST) A is called k-valued iff for every input tree there are at most k different output trees. A is called finite-valued iff it is k-valued for some k. We show: it is decidable for every k whether or not a given FST A is k-valued, and it is decidable whether or not A is finite-valued. We give an effective characterization of all finite-valued FST's and derive a (sharp) upper bound for the valuedness provided it is finite. We decompose a finite-valued FST A into a finite number of single-valued FST's. This enables us to prove: it is decidable whether or not the translation of an FST A is included in the translation of a finite-valued FST A’.

AB - A bottom-up finite state tree transducer (FST) A is called k-valued iff for every input tree there are at most k different output trees. A is called finite-valued iff it is k-valued for some k. We show: it is decidable for every k whether or not a given FST A is k-valued, and it is decidable whether or not A is finite-valued. We give an effective characterization of all finite-valued FST's and derive a (sharp) upper bound for the valuedness provided it is finite. We decompose a finite-valued FST A into a finite number of single-valued FST's. This enables us to prove: it is decidable whether or not the translation of an FST A is included in the translation of a finite-valued FST A’.

UR - http://www.scopus.com/inward/record.url?scp=85032027551&partnerID=8YFLogxK

U2 - 10.1007/3-540-52590-4_54

DO - 10.1007/3-540-52590-4_54

M3 - Conference contribution

AN - SCOPUS:85032027551

SN - 9783540525905

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 269

EP - 284

BT - CAAP 1990 - 15th Colloquium on Trees in Algebra and Programming, Proceedings

A2 - Arnold, Andre

PB - Springer Verlag

T2 - 15th Colloquium on Trees in Algebra and Programming, CAAP 1990

Y2 - 15 May 1990 through 18 May 1990

ER -

Seidl H. Equivalence of finite-valued bottom-up finite state tree transducers is decidable. In Arnold A, editor, CAAP 1990 - 15th Colloquium on Trees in Algebra and Programming, Proceedings. Springer Verlag. 1990. p. 269-284. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-52590-4_54

Equivalence of finite-valued bottom-up finite state tree transducers is decidable

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this