Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
2 results

Collapsible Pushdown Graphs of Level 2 are Tree-Automatic

Alexander Kartzow.
We show that graphs generated by collapsible pushdown systems of level 2 are tree-automatic. Even if we allow epsilon-contractions and reachability predicates (with regular constraints) for pairs of configurations, the structures remain tree-automatic whence their first-order logic theories are&nbsp;[&hellip;]
Published on March 20, 2013
Volume 9, Issue 1

Tree-Automatic Well-Founded Trees

Martin Huschenbett ; Alexander Kartzow ; Jiamou Liu ; Markus Lohrey.
We investigate tree-automatic well-founded trees. Using Delhomme's decomposition technique for tree-automatic structures, we show that the (ordinal) rank of a tree-automatic well-founded tree is strictly below omega^omega. Moreover, we make a step towards proving that the ranks of tree-automatic&nbsp;[&hellip;]
Published on June 25, 2013
Volume 9, Issue 2
  • < Previous
  • 1
  • Next >