Complexity of Regular Language Matching and Other Decidable Cases of the Satisfiability Problem for Constraints Between Regular Open Terms |
| |
Authors: | Sebastian Bala |
| |
Affiliation: | (1) Institute of Computer Science, University of Wroclaw, Przesmyckiego 20, 51151 Wroclaw, Poland |
| |
Abstract: | In this paper we study the satisfiability problem for language
equations and constraints between regular open terms. We prove
that: the constraint problem is PSPACE-complete, the regular language matching problem is EXPSPACE-complete even if we ask
about satisfiability by regular
languages, satisfiability of word-like language equations is in PSPACE, the finite solution problem is EXPSPACE-complete. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|