Variations on the Post Correspondence Problem for Free Groups

Autor:	Laura Ciobanu, Alan D. Logan
Rok vydání:	2021
Předmět:	Combinatorics Post correspondence problem Rank (linear algebra) Free monoid Free group Homomorphism Basis (universal algebra) Decision problem Mathematics Equaliser
Zdroj:	Developments in Language Theory ISBN: 9783030815073 DLT
DOI:	10.1007/978-3-030-81508-0_8
Popis:	The Post Correspondence Problem is a classical decision problem about equalisers of free monoid homomorphisms. We prove connections between several variations of this classical problem, but in the setting of free groups and free group homomorphisms. Among other results, and working under certain injectivity assumptions, we prove that computing the rank of the equaliser of a pair of free group homomorphisms can be applied to computing a basis of this equaliser, and also to solve the “generalised” Post Correspondence Problem for free groups.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::8383a3f93b2043c9283266c354740edd https://doi.org/10.1007/978-3-030-81508-0_8 Zobrazit plný text záznamu