A1 Refereed original research article in a scientific journal
Decision problems for language equations
Authors: Okhotin Alexander
Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE
Publication year: 2010
Journal: Journal of Computer and System Sciences
Journal name in source: JOURNAL OF COMPUTER AND SYSTEM SCIENCES
Journal acronym: J COMPUT SYST SCI
Volume: 76
Issue: 3-4
First page : 251
Last page: 266
Number of pages: 16
ISSN: 0022-0000
DOI: https://doi.org/10.1016/j.jcss.2009.08.002
Abstract
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
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
UTU Research Portal