Partial Automata and Finitely Generated Congruences: An Extension of Nerode's Theorem
DOI:
https://doi.org/10.7146/dpb.v21i400.6634Abstract
Let T_Sigma be the set of ground terms over a finite ranked alphabet Sigma. We define partial autornata on T_Sigma and prove that the finitely generated congruences on T_Sigma are in one-to one correspondence (up to isomorphism) with the finite partial automata on Sigma with no inaccessible and no inessential states. We give an application in term rewriting: every ground term rewrite system has a canonical equivalent system that can be constructed in polynomial time.Downloads
Published
1992-06-01
How to Cite
Kozen, D. (1992). Partial Automata and Finitely Generated Congruences: An Extension of Nerode’s Theorem. DAIMI Report Series, 21(400). https://doi.org/10.7146/dpb.v21i400.6634
Issue
Section
Articles
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.