id: 04005638
dt: j
an: 04005638
au: Brandt, U.; Walter, H.K.-G.
ti: Complete language tables.
so: Dep. Math., Karl Marx Univ. Econ., Budapest 1986-3, 13-32 (1986).
py: 1986
pu: 
la: EN
cc: 
ut: decidability; language table; two dimensional data structure; regular
    languages; standard events; dominoes; tilings; squares
ci: 
li: 
ab: A language table is a two dimensional data structure, normally a square,
    which is built up like a "crossword puzzle" associated to a language L.
    The paper deals with the problem to construct to a given language L
    language tables where no zero entries (i.e., entries different from
    letters) occur, so called complete tables. We show for example that
    whether or not there exists a language table for L of size n for some
    n, is undecidable for regular languages even defined over a two letter
    alphabet, though it is decidable for standard events. The proof shows
    that language tables are more powerful than dominoes because we can
    encode tilings of the plane, squares, etc., by complete language tables
    of very simple languages.
rv: