Polynomiální algoritmus pro pevné body netriviálních homomorphismů

Abstrakt

Článek poskytuje první polynomiální algoritmus rozhodující, zda dané konečné slovo je pevným bodem nějakého netriviálního homomorfismu. Algoritmus také sestrojí příslušný homomorfismus s minimálním možným počtem nesmazaných písmen.

Klíčová slova

• Polynomial-time
• algorithm
• fixed
• points
• nontrivial
• morphisms