Post correspondence problem for finite monoids

Clash Royale CLAN TAG#URR8PPP

up vote
5
down vote

favorite

2

The Post correspondence problem has the following version for finite monoids:

Input: a finite monoid $M$ and a finite list $(m_1,m_1'),ldots, (m_n,m_n')$ of pairs of elements of $M$

Question: is there a natural number $kgeq 1$ and indices $i_1,ldots, i_kin 1,ldots, n$ such that $m_i_1cdotcdots cdot m_i_k = m_i_1'cdotcdots cdot m_i_k'$?

Is it known whether this problem is decidable?

decidability monoid post-correspondence

share|cite|improve this question

asked Aug 13 at 21:04

user23902

261

add a comment | 

up vote
5
down vote

favorite

2

The Post correspondence problem has the following version for finite monoids:

Input: a finite monoid $M$ and a finite list $(m_1,m_1'),ldots, (m_n,m_n')$ of pairs of elements of $M$

Question: is there a natural number $kgeq 1$ and indices $i_1,ldots, i_kin 1,ldots, n$ such that $m_i_1cdotcdots cdot m_i_k = m_i_1'cdotcdots cdot m_i_k'$?

Is it known whether this problem is decidable?

decidability monoid post-correspondence

share|cite|improve this question

asked Aug 13 at 21:04

user23902

261

add a comment | 

up vote
5
down vote

favorite

2

up vote
5
down vote

favorite

2

2

The Post correspondence problem has the following version for finite monoids:

Input: a finite monoid $M$ and a finite list $(m_1,m_1'),ldots, (m_n,m_n')$ of pairs of elements of $M$

Question: is there a natural number $kgeq 1$ and indices $i_1,ldots, i_kin 1,ldots, n$ such that $m_i_1cdotcdots cdot m_i_k = m_i_1'cdotcdots cdot m_i_k'$?

Is it known whether this problem is decidable?

decidability monoid post-correspondence

share|cite|improve this question

asked Aug 13 at 21:04

user23902

261

The Post correspondence problem has the following version for finite monoids:

Input: a finite monoid $M$ and a finite list $(m_1,m_1'),ldots, (m_n,m_n')$ of pairs of elements of $M$

Question: is there a natural number $kgeq 1$ and indices $i_1,ldots, i_kin 1,ldots, n$ such that $m_i_1cdotcdots cdot m_i_k = m_i_1'cdotcdots cdot m_i_k'$?

Is it known whether this problem is decidable?

decidability monoid post-correspondence

share|cite|improve this question

asked Aug 13 at 21:04

user23902

261

share|cite|improve this question

share|cite|improve this question

asked Aug 13 at 21:04

user23902

261

asked Aug 13 at 21:04

user23902

261

asked Aug 13 at 21:04

user23902

261

261

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
9
down vote

Yes, it is decidable. Build a graph where each vertex is a pair $(r,s)$ of elements from $M$. Add all edges of the form $(r,s) to (r m_i, s m'_i)$ for all $r,s,i$. Then, your question asks whether there exists a path in this graph from the vertex $(1,1)$ to any vertex of the form $(t,t)$. This can be answered using standard reachability algorithms (e.g., DFS). The running time is linear in the size of the graph (i.e., $O(|M|^2 n)$), so the problem is decidable.

share|cite|improve this answer

answered Aug 13 at 22:40

D.W.

7,18812048

• 
  
  
  

  
  

  
  
  
  
  
  

  
  So is DFS faster than BFS here?
  – Bjørn Kjos-Hanssen♦
  Aug 13 at 22:50
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @BjørnKjos-Hanssen, no, they both run in linear time (linear in the size of the graph) so their asymptotic worst-case running time is equivalent.
  – D.W.
  Aug 13 at 23:06
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "114"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcstheory.stackexchange.com%2fquestions%2f41373%2fpost-correspondence-problem-for-finite-monoids%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
9
down vote

Yes, it is decidable. Build a graph where each vertex is a pair $(r,s)$ of elements from $M$. Add all edges of the form $(r,s) to (r m_i, s m'_i)$ for all $r,s,i$. Then, your question asks whether there exists a path in this graph from the vertex $(1,1)$ to any vertex of the form $(t,t)$. This can be answered using standard reachability algorithms (e.g., DFS). The running time is linear in the size of the graph (i.e., $O(|M|^2 n)$), so the problem is decidable.

share|cite|improve this answer

answered Aug 13 at 22:40

D.W.

7,18812048

• 
  
  
  

  
  

  
  
  
  
  
  

  
  So is DFS faster than BFS here?
  – Bjørn Kjos-Hanssen♦
  Aug 13 at 22:50
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @BjørnKjos-Hanssen, no, they both run in linear time (linear in the size of the graph) so their asymptotic worst-case running time is equivalent.
  – D.W.
  Aug 13 at 23:06
  

  
  
  
  

add a comment | 

up vote
9
down vote

Yes, it is decidable. Build a graph where each vertex is a pair $(r,s)$ of elements from $M$. Add all edges of the form $(r,s) to (r m_i, s m'_i)$ for all $r,s,i$. Then, your question asks whether there exists a path in this graph from the vertex $(1,1)$ to any vertex of the form $(t,t)$. This can be answered using standard reachability algorithms (e.g., DFS). The running time is linear in the size of the graph (i.e., $O(|M|^2 n)$), so the problem is decidable.

share|cite|improve this answer

answered Aug 13 at 22:40

D.W.

7,18812048

• 
  
  
  

  
  

  
  
  
  
  
  

  
  So is DFS faster than BFS here?
  – Bjørn Kjos-Hanssen♦
  Aug 13 at 22:50
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @BjørnKjos-Hanssen, no, they both run in linear time (linear in the size of the graph) so their asymptotic worst-case running time is equivalent.
  – D.W.
  Aug 13 at 23:06
  

  
  
  
  

add a comment | 

up vote
9
down vote

up vote
9
down vote

Yes, it is decidable. Build a graph where each vertex is a pair $(r,s)$ of elements from $M$. Add all edges of the form $(r,s) to (r m_i, s m'_i)$ for all $r,s,i$. Then, your question asks whether there exists a path in this graph from the vertex $(1,1)$ to any vertex of the form $(t,t)$. This can be answered using standard reachability algorithms (e.g., DFS). The running time is linear in the size of the graph (i.e., $O(|M|^2 n)$), so the problem is decidable.

share|cite|improve this answer

answered Aug 13 at 22:40

D.W.

7,18812048

Yes, it is decidable. Build a graph where each vertex is a pair $(r,s)$ of elements from $M$. Add all edges of the form $(r,s) to (r m_i, s m'_i)$ for all $r,s,i$. Then, your question asks whether there exists a path in this graph from the vertex $(1,1)$ to any vertex of the form $(t,t)$. This can be answered using standard reachability algorithms (e.g., DFS). The running time is linear in the size of the graph (i.e., $O(|M|^2 n)$), so the problem is decidable.

share|cite|improve this answer

answered Aug 13 at 22:40

D.W.

7,18812048

share|cite|improve this answer

share|cite|improve this answer

answered Aug 13 at 22:40

D.W.

7,18812048

answered Aug 13 at 22:40

D.W.

7,18812048

answered Aug 13 at 22:40

D.W.

7,18812048

7,18812048

• 
  
  
  

  
  

  
  
  
  
  
  

  
  So is DFS faster than BFS here?
  – Bjørn Kjos-Hanssen♦
  Aug 13 at 22:50
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @BjørnKjos-Hanssen, no, they both run in linear time (linear in the size of the graph) so their asymptotic worst-case running time is equivalent.
  – D.W.
  Aug 13 at 23:06
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  So is DFS faster than BFS here?
  – Bjørn Kjos-Hanssen♦
  Aug 13 at 22:50
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @BjørnKjos-Hanssen, no, they both run in linear time (linear in the size of the graph) so their asymptotic worst-case running time is equivalent.
  – D.W.
  Aug 13 at 23:06
  

  
  
  
  

So is DFS faster than BFS here?
– Bjørn Kjos-Hanssen♦
Aug 13 at 22:50

So is DFS faster than BFS here?
– Bjørn Kjos-Hanssen♦
Aug 13 at 22:50

1

1

@BjørnKjos-Hanssen, no, they both run in linear time (linear in the size of the graph) so their asymptotic worst-case running time is equivalent.
– D.W.
Aug 13 at 23:06

@BjørnKjos-Hanssen, no, they both run in linear time (linear in the size of the graph) so their asymptotic worst-case running time is equivalent.
– D.W.
Aug 13 at 23:06

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcstheory.stackexchange.com%2fquestions%2f41373%2fpost-correspondence-problem-for-finite-monoids%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email