Rewriting higher-order stack trees

DOI10.1007/978-3-319-20297-6_24MaRDI QIDQ3194729zbMATH OpenOpenAlexFDO

Authors Vincent Penelle

Publication date 20 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.04653

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Abstract: Higher-order pushdown systems and ground tree rewriting systems can be seen as extensions of suffix word rewriting systems. Both classes generate infinite graphs with interesting logical properties. Indeed, the model-checking problem for monadic second order logic (respectively first order logic with a reachability predicate) is decidable on such graphs. We unify both models by introducing the notion of stack trees, trees whose nodes are labelled by higher-order stacks, and define the corresponding class of higher-order ground tree rewriting systems. We show that these graphs retain the decidability properties of ground tree rewriting graphs while generalising the pushdown hierarchy of graphs.

Recommendations

• Rewriting higher-order stack trees
• scientific article; zbMATH DE number 2087432
• First-order logic on higher-order nested pushdown trees
• scientific article; zbMATH DE number 2087437
• Mathematical Foundations of Computer Science 2005

Cites work

• scientific article; zbMATH DE number 1222589 (Why is no real title available?)
• scientific article; zbMATH DE number 1929935 (Why is no real title available?)
• scientific article; zbMATH DE number 2087432 (Why is no real title available?)
• scientific article; zbMATH DE number 2102748 (Why is no real title available?)
• A Saturation Method for Collapsible Pushdown Systems
• Collapsible pushdown automata and labeled recursion schemes, equivalence, safety and effective selection
• Decidability of second-order theories and automata on infinite trees
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Finite presentations of infinite structures: Automata and interpretations
• Mathematical Foundations of Computer Science 2005
• The synchronized graphs trace the context-sensitive languages
• Traces of term-automatic graphs
• Transforming structures by set interpretations

Cited in

(8)

• scientific article; zbMATH DE number 2087432 (Why is no real title available?)
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Ordered tree-pushdown systems
• Mathematical Foundations of Computer Science 2005
• From Stack Traces to Lazy Rewriting Sequences
• scientific article; zbMATH DE number 2087437 (Why is no real title available?)
• Rewriting higher-order stack trees
• scientific article; zbMATH DE number 2086416 (Why is no real title available?)

This page was built for publication: Rewriting higher-order stack trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3194729)