@InProceedings{ABA:98:ICALP,
  author =       "Amir M. Ben-Amram and Holger Petersen",
  year =         "1998",
  title =        "Cons-free Programs with Tree Input",
  booktitle =    "Proceedings, 25th Int. Colloquium on Automata,
                 Languages and Programming (ICALP)",
  editor =       "Kim G. Larsen and Sven Skyum and Glynn Winskel",
  publisher =    "Springer",
  series =       "LNCS",
  volume =       "1443",
  pages =        "271--282",
  keywords =     "computability in subrecursive langauges, complexity
                 classes, multi-head automata",
  summary =      "We investigate the expressive power of programs
                 operating on an input which is a LISP-style tree
                 without the possibility to modify or create cons cells.
                 They can thus apply car or cdr but not cons. We obtain
                 a hierarchy of classes of sets that can be recognized
                 by deterministic, non-deterministic and recursive
                 programs respectively, with and without the additionl
                 operation of testing pointer equality. Several results
                 on the relationship of the classes defined by these
                 languages to Turing-machine based complexity classes
                 are obtained.",
  puf =          "Artikel i proceedings (med censur)",
}