You are here: TUCS > PUBLICATIONS > Publication Search > Univariate Equations Over Sets...
- TUCS Publication Series
- How to Publish in TUCS Series
- Publication Search
- Publication Graph
- Publication Input
- Publication Input Guide
- JuFo Browser
Univariate Equations Over Sets of Natural Numbers
Artur Jez, Alexander Okhotin, Univariate Equations Over Sets of Natural Numbers. TUCS Technical Reports 913, Turku Centre for Computer Science, 2008.
Abstract:
It is shown that equations <i>X</i>=φ(<i>X</i>),
in which the unknown <i>X</i> is a set of natural numbers
and φ uses operations of union, intersection
and addition <i>S</i> + <i>T</i> =
{<i>m</i>+<i>n</i> | <i>m</i>∈<i>S</i>, <i>n</i>∈<i>T</i>},
can simulate systems of equations
<i>X<sub>i</sub></i>=φ(<i>X</i><sub>1</sub>, …, <i>X</i><sub><i>n</i></sub>)
with 1 ≤ <i>i</i> ≤ <i>n</i>,
in the sense that the solution of a system
is encoded in the solution of an equation.
This implies undecidability of some properties
of one-nonterminal conjunctive grammars
over a unary alphabet.
In a relatively similar way,
equations φ(<i>X</i>)=ψ(<i>X</i>)
can simulate systems of such equations
with multiple variables,
which implies computational universality
of their least and greatest solutions, as well as
undecidability of their basic decision problems.
In both constructions
it is sufficient to use only singleton constants.
Files:
Full publication in PDF-format
BibTeX entry:
@TECHREPORT{tJeOk08b,
title = {Univariate Equations Over Sets of Natural Numbers},
author = {Jez, Artur and Okhotin, Alexander},
number = {913},
series = {TUCS Technical Reports},
publisher = {Turku Centre for Computer Science},
year = {2008},
keywords = {Language equations, conjunctive grammars, decision problems},
ISBN = {978-952-12-2149-1},
}
Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics