文章基本信息

标题：Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups
本地全文：下载
作者：Volker Diekert ; Murray Elder
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：96:1-96:14
DOI：10.4230/LIPIcs.ICALP.2017.96
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We prove that the full solution set of a twisted word equation with regular constraints is an EDT0L language. It follows that the set of solutions to equations with rational constraints in a context-free group (= finitely generated virtually free group) in reduced normal forms is EDT0L. We can also decide whether or not the solution set is finite, which was an open problem. Moreover, this can all be done in PSPACE. Our results generalize the work by Lohrey and Senizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to complexity and with respect to expressive power. Both papers show that satisfiability is decidable, but neither gave any concrete complexity bound. Our results concern all solutions, and give, in some sense, the "optimal" formal language characterization.
关键词：Twisted word equation; EDT0L; virtually free group; context-free group