文章基本信息

标题：Complexity of solutions of equations over sets of natural numbers
本地全文：下载
作者：Alexander Okhotin ; Artur Jez
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2008
卷号：1
页码：373-384
DOI：10.4230/LIPIcs.STACS.2008.1319
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Systems of equations over sets of natural numbers (or, equivalently, language equations over a one-letter alphabet) of the form $X_i=varphi_i(X_1, ldots, X_n)$ ($1 leqslant i leqslant n$) are considered. Expressions $varphi_i$ may contain the operations of union, intersection and pairwise sum $A plus B = {x + y mid x in A, y in B$. A system with an EXPTIME-complete least solution is constructed, and it is established that least solutions of all such systems are in EXPTIME. The general membership problem for these equations is proved to be EXPTIME-complete.