Complexity of E0L structural equivalence
Kai Salomaa, Derick Wood, Sheng Yü · RAIRO - Theoretical Informatics and Applications · 1995
We show that the EOL structural équivalence problem is logspace hard for deterministic exponential time.Also, we show that this question can be solved in linear space by a synchronized alternating Turing machine, and thus establish an exponential space upper boundfor its complexity.The équivalence offinite tree automata is shown to be logspace reducible to context-free structural équivalence.The converse réduction is well known and thus context-free structural équivalence is complete for deterministic exponential time.Résumé.-Nous prouvons que l'équivalence structurelle des EOL-systèmes est difficile en espace logarithmique et temps déterministe exponentiel.Nous montrons également que cette question peut être résolue en espace linéaire par une machine de Turing alternante, ce qui établit une borne supérieure exponentielle en place pour sa complexité.On prouve que l'équivalence d'automates finies d'arbres est réductible en place logarithmique à l'équivalence structurelle des langages algébriques.La réduction réciproque est bien connue, et ainsi l'équivalence structurelle des langages algébrique est complète pour le temps exponentiel déterministe.