Decision problems for language equations



: Okhotin Alexander

Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE

: 2010

: Journal of Computer and System Sciences

: JOURNAL OF COMPUTER AND SYSTEM SCIENCES

: J COMPUT SYST SCI

: 76

: 3-4

: 251

: 266

: 16

: 0022-0000

DOI: https://doi.org/10.1016/j.jcss.2009.08.002


Equations with formal languages as unknowns using all Boolean operations and concatenation are studied. Their main properties, such as solution existence and uniqueness, are characterized by first-order formulae. It is shown that testing solution existence is Pi(1)-complete, while solution uniqueness and existence of a least and of a greatest solution are all Pi(2)-complete problems The families of languages defined by components of unique. least and greatest solutions of such systems are shown to coincide with the classes of recursive, recursively enumerable and co-recursively enumerable sets, respectively (C) 2009 Elsevier Inc. All rights reserved



Last updated on 2024-26-11 at 22:55