RACSO
R
DFA
CFG
Operations:
Reg
,
CF
PDA
Reductions:
K
,
WP
,
CFG
,
NP
,
SAT
ANTLR:
lex
,
syn
Exams
log in
,
register
,
guest
This site uses cookies only for the purpose of identifying user sessions. This is required to properly register actions.
Exercises on reductions of programs
K
≤
{
p
∣
∃
y
:
M
p
(
y
)
↓
}
K\;\leq\;\{ p \mid \exists y:\;M_p(y){\downarrow} \}
K
≤
{
p
∣
∃
y
:
M
p
(
y
)
↓
}
K
‾
≤
{
p
∣
∀
y
:
M
p
(
y
)
↓
}
\overline{K}\;\leq\;\{ p \mid \forall y:\;M_p(y){\downarrow} \}
K
≤
{
p
∣
∀
y
:
M
p
(
y
)
↓
}
K
‾
≤
{
p
∣
∃
y
:
M
p
(
y
)
↑
}
\overline{K}\;\leq\;\{ p \mid \exists y:\;M_p(y){\uparrow} \}
K
≤
{
p
∣
∃
y
:
M
p
(
y
)
↑
}
K
‾
≤
{
p
∣
∀
y
:
M
p
(
y
)
↑
}
\overline{K}\;\leq\;\{ p \mid \forall y:\;M_p(y){\uparrow} \}
K
≤
{
p
∣
∀
y
:
M
p
(
y
)
↑
}
K
‾
≤
{
p
∣
∀
y
:
M
p
(
y
)
=
y
}
\overline{K}\;\leq\;\{ p \mid \forall y:\;M_p(y)=y \}
K
≤
{
p
∣
∀
y
:
M
p
(
y
)
=
y
}
K
‾
≤
{
p
∣
φ
p
total and injective
}
\overline{K}\;\leq\;\{ p \mid \varphi_p\text{ total and injective} \}
K
≤
{
p
∣
φ
p
total and injective
}
K
‾
≤
{
p
∣
φ
p
total and non-injective
}
\overline{K}\;\leq\;\{ p \mid \varphi_p\text{ total and non-injective} \}
K
≤
{
p
∣
φ
p
total and non-injective
}
K
‾
≤
{
p
∣
M
p
(
1
)
↓
∧
M
p
(
2
)
↑
}
\overline{K}\;\leq\;\{ p \mid M_p(1){\downarrow} \,\wedge\, M_p(2){\uparrow} \}
K
≤
{
p
∣
M
p
(
1
)
↓
∧
M
p
(
2
)
↑
}
K
≤
{
p
∣
∣
D
o
m
(
φ
p
)
∣
≥
2
}
K\;\leq\;\{ p \mid |\mathtt{Dom}(\varphi_p)|\geq 2 \}
K
≤
{
p
∣
∣
Dom
(
φ
p
)
∣
≥
2
}
K
‾
≤
{
p
∣
∣
D
o
m
(
φ
p
)
∣
=
2
}
\overline{K}\;\leq\;\{ p \mid |\mathtt{Dom}(\varphi_p)|=2 \}
K
≤
{
p
∣
∣
Dom
(
φ
p
)
∣
=
2
}
K
≤
{
p
∣
∣
I
m
(
φ
p
)
∣
≥
2
}
K\;\leq\;\{ p \mid |\mathtt{Im}(\varphi_p)|\geq 2 \}
K
≤
{
p
∣
∣
Im
(
φ
p
)
∣
≥
2
}
K
‾
≤
{
p
∣
∣
I
m
(
φ
p
)
∣
=
2
}
\overline{K}\;\leq\;\{ p \mid |\mathtt{Im}(\varphi_p)|=2 \}
K
≤
{
p
∣
∣
Im
(
φ
p
)
∣
=
2
}
K
‾
≤
{
p
∣
∣
D
o
m
(
φ
p
)
∣
=
∞
∧
∣
I
m
(
φ
p
)
∣
=
∞
∧
D
o
m
(
φ
p
)
∩
I
m
(
φ
p
)
=
∅
}
\overline{K}\;\leq\;\{ p \mid |\mathtt{Dom}(\varphi_p)|=\infty\;\wedge\;|\mathtt{Im}(\varphi_p)|=\infty\;\wedge\;\mathtt{Dom}(\varphi_p)\cap\mathtt{Im}(\varphi_p)=\emptyset \}
K
≤
{
p
∣
∣
Dom
(
φ
p
)
∣
=
∞
∧
∣
Im
(
φ
p
)
∣
=
∞
∧
Dom
(
φ
p
)
∩
Im
(
φ
p
)
=
∅
}
K
≤
{
⟨
p
,
q
⟩
∣
∃
y
:
(
M
p
(
y
)
↓
∧
M
q
(
y
)
↓
)
}
K\;\leq\;\{ \langle p,q\rangle \mid \exists y:\;(M_p(y){\downarrow} \,\wedge\, M_q(y){\downarrow}) \}
K
≤
{⟨
p
,
q
⟩
∣
∃
y
:
(
M
p
(
y
)
↓
∧
M
q
(
y
)
↓
)}
K
‾
≤
{
⟨
p
,
q
⟩
∣
∃
y
:
(
M
p
(
y
)
↓
∧
M
q
(
y
)
↑
)
}
\overline{K}\;\leq\;\{ \langle p,q\rangle \mid \exists y:\;(M_p(y){\downarrow} \,\wedge\, M_q(y){\uparrow}) \}
K
≤
{⟨
p
,
q
⟩
∣
∃
y
:
(
M
p
(
y
)
↓
∧
M
q
(
y
)
↑
)}
K
‾
≤
{
⟨
p
,
q
⟩
∣
∃
y
1
,
y
2
:
(
M
p
(
y
1
)
↓
∧
M
q
(
y
1
)
↑
∧
M
p
(
y
2
)
↑
∧
M
q
(
y
2
)
↓
)
}
\overline{K}\;\leq\;\{ \langle p,q\rangle \mid \exists y_1,y_2:\;(M_p(y_1){\downarrow} \,\wedge\, M_q(y_1){\uparrow} \,\wedge\, M_p(y_2){\uparrow} \,\wedge\, M_q(y_2){\downarrow}) \}
K
≤
{⟨
p
,
q
⟩
∣
∃
y
1
,
y
2
:
(
M
p
(
y
1
)
↓
∧
M
q
(
y
1
)
↑
∧
M
p
(
y
2
)
↑
∧
M
q
(
y
2
)
↓
)}
K
≤
{
⟨
p
,
q
⟩
∣
∣
D
o
m
(
φ
p
)
∩
D
o
m
(
φ
q
)
∣
≥
2
}
K\;\leq\;\{ \langle p,q\rangle \mid |\mathtt{Dom}(\varphi_p)\cap\mathtt{Dom}(\varphi_q)|\geq 2 \}
K
≤
{⟨
p
,
q
⟩
∣
∣
Dom
(
φ
p
)
∩
Dom
(
φ
q
)
∣
≥
2
}
K
‾
≤
{
⟨
p
,
q
⟩
∣
∣
D
o
m
(
φ
p
)
∩
D
o
m
(
φ
q
)
∣
=
2
}
\overline{K}\;\leq\;\{ \langle p,q\rangle \mid |\mathtt{Dom}(\varphi_p)\cap\mathtt{Dom}(\varphi_q)|=2 \}
K
≤
{⟨
p
,
q
⟩
∣
∣
Dom
(
φ
p
)
∩
Dom
(
φ
q
)
∣
=
2
}
K
‾
≤
{
⟨
p
,
q
⟩
∣
∣
D
o
m
(
φ
p
)
∣
=
∣
D
o
m
(
φ
q
)
∣
=
∣
I
m
(
φ
p
)
∣
=
∣
I
m
(
φ
q
)
∣
=
1
∧
∣
D
o
m
(
φ
p
)
∪
D
o
m
(
φ
q
)
∪
I
m
(
φ
p
)
∪
I
m
(
φ
q
)
∣
=
1
}
\overline{K}\;\leq\;\{ \langle p,q\rangle \mid |\mathtt{Dom}(\varphi_p)|=|\mathtt{Dom}(\varphi_q)|=|\mathtt{Im}(\varphi_p)|=|\mathtt{Im}(\varphi_q)|=1\;\wedge\;|\mathtt{Dom}(\varphi_p)\cup\mathtt{Dom}(\varphi_q)\cup\mathtt{Im}(\varphi_p)\cup\mathtt{Im}(\varphi_q)|=1 \}
K
≤
{⟨
p
,
q
⟩
∣
∣
Dom
(
φ
p
)
∣
=
∣
Dom
(
φ
q
)
∣
=
∣
Im
(
φ
p
)
∣
=
∣
Im
(
φ
q
)
∣
=
1
∧
∣
Dom
(
φ
p
)
∪
Dom
(
φ
q
)
∪
Im
(
φ
p
)
∪
Im
(
φ
q
)
∣
=
1
}
K
‾
≤
{
⟨
p
,
q
⟩
∣
∣
D
o
m
(
φ
p
)
∣
=
∣
D
o
m
(
φ
q
)
∣
=
∣
I
m
(
φ
p
)
∣
=
∣
I
m
(
φ
q
)
∣
=
1
∧
∣
D
o
m
(
φ
p
)
∪
D
o
m
(
φ
q
)
∪
I
m
(
φ
p
)
∪
I
m
(
φ
q
)
∣
=
2
}
\overline{K}\;\leq\;\{ \langle p,q\rangle \mid |\mathtt{Dom}(\varphi_p)|=|\mathtt{Dom}(\varphi_q)|=|\mathtt{Im}(\varphi_p)|=|\mathtt{Im}(\varphi_q)|=1\;\wedge\;|\mathtt{Dom}(\varphi_p)\cup\mathtt{Dom}(\varphi_q)\cup\mathtt{Im}(\varphi_p)\cup\mathtt{Im}(\varphi_q)|=2 \}
K
≤
{⟨
p
,
q
⟩
∣
∣
Dom
(
φ
p
)
∣
=
∣
Dom
(
φ
q
)
∣
=
∣
Im
(
φ
p
)
∣
=
∣
Im
(
φ
q
)
∣
=
1
∧
∣
Dom
(
φ
p
)
∪
Dom
(
φ
q
)
∪
Im
(
φ
p
)
∪
Im
(
φ
q
)
∣
=
2
}
K
‾
≤
{
⟨
p
,
q
⟩
∣
∣
D
o
m
(
φ
p
)
∣
=
∣
D
o
m
(
φ
q
)
∣
=
∣
I
m
(
φ
p
)
∣
=
∣
I
m
(
φ
q
)
∣
=
1
∧
∣
D
o
m
(
φ
p
)
∪
D
o
m
(
φ
q
)
∪
I
m
(
φ
p
)
∪
I
m
(
φ
q
)
∣
=
3
}
\overline{K}\;\leq\;\{ \langle p,q\rangle \mid |\mathtt{Dom}(\varphi_p)|=|\mathtt{Dom}(\varphi_q)|=|\mathtt{Im}(\varphi_p)|=|\mathtt{Im}(\varphi_q)|=1\;\wedge\;|\mathtt{Dom}(\varphi_p)\cup\mathtt{Dom}(\varphi_q)\cup\mathtt{Im}(\varphi_p)\cup\mathtt{Im}(\varphi_q)|=3 \}
K
≤
{⟨
p
,
q
⟩
∣
∣
Dom
(
φ
p
)
∣
=
∣
Dom
(
φ
q
)
∣
=
∣
Im
(
φ
p
)
∣
=
∣
Im
(
φ
q
)
∣
=
1
∧
∣
Dom
(
φ
p
)
∪
Dom
(
φ
q
)
∪
Im
(
φ
p
)
∪
Im
(
φ
q
)
∣
=
3
}
K
‾
≤
{
⟨
p
,
q
⟩
∣
∣
D
o
m
(
φ
p
)
∣
=
∣
D
o
m
(
φ
q
)
∣
=
∣
I
m
(
φ
p
)
∣
=
∣
I
m
(
φ
q
)
∣
=
1
∧
∣
D
o
m
(
φ
p
)
∪
D
o
m
(
φ
q
)
∪
I
m
(
φ
p
)
∪
I
m
(
φ
q
)
∣
=
4
}
\overline{K}\;\leq\;\{ \langle p,q\rangle \mid |\mathtt{Dom}(\varphi_p)|=|\mathtt{Dom}(\varphi_q)|=|\mathtt{Im}(\varphi_p)|=|\mathtt{Im}(\varphi_q)|=1\;\wedge\;|\mathtt{Dom}(\varphi_p)\cup\mathtt{Dom}(\varphi_q)\cup\mathtt{Im}(\varphi_p)\cup\mathtt{Im}(\varphi_q)|=4 \}
K
≤
{⟨
p
,
q
⟩
∣
∣
Dom
(
φ
p
)
∣
=
∣
Dom
(
φ
q
)
∣
=
∣
Im
(
φ
p
)
∣
=
∣
Im
(
φ
q
)
∣
=
1
∧
∣
Dom
(
φ
p
)
∪
Dom
(
φ
q
)
∪
Im
(
φ
p
)
∪
Im
(
φ
q
)
∣
=
4
}
K
‾
≤
{
⟨
p
,
q
⟩
∣
D
o
m
(
φ
p
)
⊆
D
o
m
(
φ
q
)
}
\overline{K}\;\leq\;\{ \langle p,q\rangle \mid \mathtt{Dom}(\varphi_p)\subseteq\mathtt{Dom}(\varphi_q) \}
K
≤
{⟨
p
,
q
⟩
∣
Dom
(
φ
p
)
⊆
Dom
(
φ
q
)}
K
‾
≤
{
⟨
p
,
q
⟩
∣
D
o
m
(
φ
p
)
⊂
D
o
m
(
φ
q
)
}
\overline{K}\;\leq\;\{ \langle p,q\rangle \mid \mathtt{Dom}(\varphi_p)\subset\mathtt{Dom}(\varphi_q) \}
K
≤
{⟨
p
,
q
⟩
∣
Dom
(
φ
p
)
⊂
Dom
(
φ
q
)}
K
‾
≤
{
⟨
p
,
q
⟩
∣
D
o
m
(
φ
p
)
⊂
D
o
m
(
φ
q
)
⊂
I
m
(
φ
p
)
}
\overline{K}\;\leq\;\{ \langle p,q\rangle \mid \mathtt{Dom}(\varphi_p)\subset\mathtt{Dom}(\varphi_q)\subset\mathtt{Im}(\varphi_p) \}
K
≤
{⟨
p
,
q
⟩
∣
Dom
(
φ
p
)
⊂
Dom
(
φ
q
)
⊂
Im
(
φ
p
)}
K
‾
≤
{
⟨
p
,
q
⟩
∣
∣
D
o
m
(
φ
p
)
∣
=
∞
∧
∣
D
o
m
(
φ
q
)
∣
=
∞
∧
D
o
m
(
φ
p
)
∩
D
o
m
(
φ
q
)
=
∅
}
\overline{K}\;\leq\;\{ \langle p,q\rangle \mid |\mathtt{Dom}(\varphi_p)|=\infty\;\wedge\;|\mathtt{Dom}(\varphi_q)|=\infty\;\wedge\;\mathtt{Dom}(\varphi_p)\cap\mathtt{Dom}(\varphi_q)=\emptyset \}
K
≤
{⟨
p
,
q
⟩
∣
∣
Dom
(
φ
p
)
∣
=
∞
∧
∣
Dom
(
φ
q
)
∣
=
∞
∧
Dom
(
φ
p
)
∩
Dom
(
φ
q
)
=
∅
}
K
‾
≤
{
⟨
p
,
q
⟩
∣
∣
D
o
m
(
φ
p
)
∣
=
∞
∧
∣
D
o
m
(
φ
q
)
∣
=
∞
∧
D
o
m
(
φ
p
)
∩
D
o
m
(
φ
q
)
=
∅
∧
∀
y
:
∣
D
o
m
(
φ
p
)
∩
{
0
,
…
,
y
}
∣
>
∣
D
o
m
(
φ
q
)
∩
{
0
,
…
,
y
}
∣
}
\overline{K}\;\leq\;\{ \langle p,q\rangle \mid |\mathtt{Dom}(\varphi_p)|=\infty\;\wedge\;|\mathtt{Dom}(\varphi_q)|=\infty\;\wedge\;\mathtt{Dom}(\varphi_p)\cap\mathtt{Dom}(\varphi_q)=\emptyset\;\wedge\;\forall y:|\mathtt{Dom}(\varphi_p)\cap\{0,\ldots,y\}|>|\mathtt{Dom}(\varphi_q)\cap\{0,\ldots,y\}| \}
K
≤
{⟨
p
,
q
⟩
∣
∣
Dom
(
φ
p
)
∣
=
∞
∧
∣
Dom
(
φ
q
)
∣
=
∞
∧
Dom
(
φ
p
)
∩
Dom
(
φ
q
)
=
∅
∧
∀
y
:
∣
Dom
(
φ
p
)
∩
{
0
,
…
,
y
}
∣
>
∣
Dom
(
φ
q
)
∩
{
0
,
…
,
y
}
∣
}