@article{BordihnBottoniLabellaetal.2017,
  author    = {Bordihn, Henning and Bottoni, Paolo and Labella, Anna and Mitrana, Victor},
  title     = {Networks of picture processors as problem solvers},
  series = {Soft Computing},
  volume    = {21},
  journal   = {Soft Computing},
  publisher = {Springer},
  address   = {New York},
  issn      = {1432-7643},
  doi       = {10.1007/s00500-016-2206-y},
  pages     = {5529 -- 5541},
  year      = {2017},
  abstract  = {We propose a solution based on networks of picture processors to the problem of picture pattern matching. The network solving the problem can be informally described as follows: it consists of two subnetworks, one of them extracts at each step, simultaneously, all subpictures of identical (progressively decreasing) size from the input picture and sends them to the other subnetwork which checks whether any of the received pictures is identical to the pattern. We present an efficient solution based on networks with evolutionary processors only, for patterns with at most three rows or columns. Afterward, we present a solution based on networks containing both evolutionary and hiding processors running in O(n + m + kl) computational (processing and communication) steps, for any size (n, m) of the input pic-ture and (k, l) of the pattern. From the proofs of these results, we infer that any (k, l)-local language with 1 <= k <= 3 can be decided in O(n + m + l) computational steps by networks with evolutionary processors only, while any (k, l)-local language with arbitrary k, l can be decided in O(n + m + kl) computational steps by networks containing both evolutionary and hiding processors.},
  language  = {en}
}
@article{Bordihn2017,
  author    = {Bordihn, Henning},
  title     = {Active symbols in grammars with valuations},
  series = {Theoretical computer science},
  volume    = {682},
  journal   = {Theoretical computer science},
  publisher = {Elsevier},
  address   = {Amsterdam},
  issn      = {0304-3975},
  doi       = {10.1016/j.tcs.2016.11.008},
  pages     = {42 -- 48},
  year      = {2017},
  abstract  = {Grammars with valuations are context-free rewriting mechanisms where the derivation process is controlled by a recursive function that evaluates strings. They have been introduced by Jurgen Dassow as models for the molecular replication process taking into account its selective character. A symbol is active in a grammar with valuation if it can be rewritten non-identically. This paper studies the effect of restricting the number of active symbols in grammars with valuations and several variants thereof to their generative power. It is investigated in which cases the number of active symbols induces infinite strict hierarchies and when the hierarchies collapse. The induced language families are compared among one another. (C) 2016 Elsevier B.V. All rights reserved.},
  language  = {en}
}