Decidability and closure properties of equational tree languages

DOI10.1007/3-540-45610-4_9MaRDI QIDQ4808742zbMATH OpenFDO

Authors Hitoshi Ohsaki, Toshinori Takai

Publication date 12 August 2004

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

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2378/23780114.htm

Mathematics Subject Classification ID

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

Recommendations

• Beyond regularity: Equational tree automata for associative and commutative theories
• Combining Equational Tree Automata over AC and ACI Theories
• Tree automata help one to solve equational formulae in AC-theories
• Two-way equational tree automata for AC-like theories: Decidability and closure properties
• On closure under complementation of equational tree automata for theories extending AC

Cited in

(11)

• Alternating two-way AC-tree automata
• Tree automata with equality constraints modulo equational theories
• Nested semantics over finite trees are equationally hard (invited talk)
• On closure under complementation of equational tree automata for theories extending AC
• Combining Equational Tree Automata over AC and ACI Theories
• Propositional Tree Automata
• Axiomatizing the equational theory of regular tree languages. (Extended abstract)
• Two-way equational tree automata for AC-like theories: Decidability and closure properties
• Recognizing Boolean closed A-tree languages with membership conditional rewriting mechanism
• Beyond regularity: Equational tree automata for associative and commutative theories
• Monotone AC-Tree Automata

This page was built for publication: Decidability and closure properties of equational tree languages

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