@inproceedings{cc00fe4a8a1142498e772321a82d35c8,
title = "Deciding Equivalence of Separated Non-nested Attribute Systems in Polynomial Time",
abstract = "In 1982, Courcelle and Franchi-Zannettacci showed that the equivalence problem of separated non-nested attribute systems can be reduced to the equivalence problem of total deterministic separated basic macro tree transducers. They also gave a procedure for deciding equivalence of transducer in the latter class. Here, we reconsider this equivalence problem. We present a new alternative decision procedure and prove that it runs in polynomial time. We also consider extensions of this result to partial transducers and to the case where parameters of transducers accumulate strings instead of trees.",
author = "Helmut Seidl and Raphaela Palenta and Sebastian Maneth",
note = "Publisher Copyright: {\textcopyright} 2019, The Author(s).; 22nd International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2019 Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019 ; Conference date: 06-04-2019 Through 11-04-2019",
year = "2019",
doi = "10.1007/978-3-030-17127-8_28",
language = "English",
isbn = "9783030171261",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "488--504",
editor = "Alex Simpson and Mikolaj Bojanczyk",
booktitle = "Foundations of Software Science and Computation Structures - 22nd International Conference, FOSSACS 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Proceedings",
}