Rewrite Closure and CF Hedge Automata

DOI10.1007/978-3-642-37064-9_33MaRDI QIDQ4910476zbMATH OpenOpenAlexFDO

Authors Florent Jacquemard, Michaël Rusinowitch

Publication date 18 March 2013

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We introduce an extension of hedge automata called bidimensional context-free hedge automata. The class of unranked ordered tree languages they recognize is shown to be preserved by rewrite closure with inverse-monadic rules. We also extend the parameterized rewriting rules used for modeling the W3C XQuery Update Facility in previous works, by the possibility to insert a new parent node above a given node. We show that the rewrite closure of hedge automata languages with these extended rewriting systems are context-free hedge languages.

Recommendations

• Closure of Hedge-Automata Languages by Hedge Rewriting
• Closure of tree automata languages under innermost rewriting
• -clearing restarting automata and CFL
• Infinitary rewriting: closure operators, equivalences and models
• scientific article; zbMATH DE number 1254101
• Invariants and closures in the theory of rewrite systems
• One-variable context-free hedge automata
• Regularity and context-freeness over word rewriting systems
• Applications and extensions of context-sensitive rewriting
• Closure of finite-state automaton languages

Cited in

(4)

• One-variable context-free hedge automata
• Term rewriting with prefix context constraints and bottom-up strategies
• Closure of Hedge-Automata Languages by Hedge Rewriting
• Regular hedge language factorization revisited

This page was built for publication: Rewrite Closure and CF Hedge Automata

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