Two-letter group codes that preserve aperiodicity of inverse finite automata |
| |
Authors: | Jean-Camille Birget Stuart W Margolis |
| |
Institution: | (1) Dept. of Computer Science, Rutgers University at Camden, Camden, NJ 08102, USA;(2) Dept. of Mathematics, Bar Ilan University, Ramat Gan, 52900, Israel |
| |
Abstract: | We construct group codes over two letters (i.e., bases of subgroups of a two-generated free group) with special properties.
Such group codes can be used for reducing algorithmic problems over large alphabets to algorithmic problems over a two-letter
alphabet. Our group codes preserve aperiodicity of inverse finite automata. As an application we show that the following problems
are PSpace-complete for two-letter alphabets (this was previously known for large enough finite alphabets): The intersection-emptiness problem for inverse finite
automata, the aperiodicity problem for inverse finite automata, and the closure-under-radical problem for finitely generated
subgroups of a free group. The membership problem for 3-generated inverse monoids is PSpace-complete.
Both authors were supported in part by NSF grant DMS-9970471. The first author was also supported in part by NSF grant CCR-0310793.
The second author acknowledges the support of the Excellency Center, “Group Theoretic Methods for the Study of Algebraic Varieties”
of the Israeli Science Foundation. |
| |
Keywords: | Free groups Inverse semigroups Inverse automata |
本文献已被 SpringerLink 等数据库收录! |
|