Auflistung nach Autor "Borchert, Bernd"

Sortiert nach: Sortierung: Ergebnisse:

  • The atnext/atprevious hierarchy on the starfree languages 
    Borchert, Bernd; Tesson, Pascal (2004)
    The temporal logic operators atnext and atprevious are alternatives for the operators until and since. P atnext Q has the meaning: at the next position in the future where Q holds it holds P. We define an asymmetric but ...
  • Deterministically and Sudoku-Deterministically Recognizable Picture Languages 
    Borchert, Bernd; Reinhardt, Klaus (2006)
    The recognizable 2-dimensional languages are a robust class with many characterizations, comparable to the regular languages in the 1-dimensional case. One characterization is by tiling systems. The corresponding word ...
  • The dot-depth and the polynomial hierarchy correspond on the delta levels 
    Borchert, Bernd; Lange, Klaus-Joern; Stephan, Frank; Tesson, Pascal; Therien, Denis (2004)
    It is well-known that the Sigma_k- and Pi_k-levels of the dot-depth hierarchy and the polynomial hierarchy correspond via leaf languages. In this paper this correspondence will be extended to the Delta_k-levels of these ...
  • The dot-depth hierarchy versus iterated block products of DA 
    Borchert, Bernd (2004)
    Like the sequence of the classes of the dot-depth hierarchy the sequence of classes given by the n-fold iterated block product of DA has the class of starfree regular languages as its limit. It is shown that this ...
  • Exponential Multiplication Schemes 
    Borchert, Bernd; Reinhardt, Klaus (2006)
    We present an idea to describe a polynomial with 2^n distinct integer zeros by an n-tuple of integers via a scheme of n recurring equations. We call such an n-tuple an exponential multiplication scheme of size n. Exponential ...
  • Formal Language Characterizations of P, NP, and PSPACE 
    Borchert, Bernd (2003)
    Giammarresi & Restivo (1992) define locality and recognizability for 2-dimensional languages. Based on these notions, generalized to the n-dimensional case, n-dimensionally colorable 1-dimensional languages are introduced. It ...
  • Searching paths of constant bandwidth 
    Borchert, Bernd; Reinhardt, Klaus (2004)
    As a generalization of paths, the notion of paths of bandwidth w is introduced. We show that, for a given constant w >= 1, the corresponding search problem for such a path of length k in a given graph is NP-complete and ...
  • Segment-based Visual Cryptography 
    Borchert, Bernd (2007)
    A version of Visual Cryptography is presented which is not pixel-based but segment-based. It is used to encrypt messages consisting of symbols which can be represented by a segment display. For example, the decimal digits ...