A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Decision problems for language equations
Tekijät: Okhotin Alexander
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2010
Journal: Journal of Computer and System Sciences
Tietokannassa oleva lehden nimi: JOURNAL OF COMPUTER AND SYSTEM SCIENCES
Lehden akronyymi: J COMPUT SYST SCI
Vuosikerta: 76
Numero: 3-4
Aloitussivu: 251
Lopetussivu: 266
Sivujen määrä: 16
ISSN: 0022-0000
DOI: https://doi.org/10.1016/j.jcss.2009.08.002
Tiivistelmä
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
Turun yliopiston Tutkimustietojärjestelmän portaali