Two-way equational tree automata for AC-like theories: Decidability and closure properties

DOI10.1007/3-540-44881-0_14MaRDI QIDQ4447233zbMATH OpenFDO

Authors Kumar Neeraj Verma

Publication date 16 February 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/2706/27060180.htm

zbMATH Keywords

alternationemptinessequational theoriestwo-way tree automata

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Automata and formal grammars in connection with logical questions (03D05) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• On closure under complementation of equational tree automata for theories extending AC
• Combining Equational Tree Automata over AC and ACI Theories
• Tree automata help one to solve equational formulae in AC-theories
• Decidability and closure properties of equational tree languages
• Tree Automata with Equality Constraints Modulo Equational Theories
• Tree automata with equality constraints modulo equational theories
• Beyond regularity: Equational tree automata for associative and commutative theories
• scientific article; zbMATH DE number 512857
• Alternating two-way AC-tree automata
• A survey on decidable equivalence problems for tree transducers

Cited in

(10)

• Multitree automata that count
• Alternating two-way AC-tree automata
• Tree automata with equality constraints modulo equational theories
• Abstraction and resolution modulo AC: How to verify Diffie--Hellman-like protocols automatically
• On closure under complementation of equational tree automata for theories extending AC
• Combining Equational Tree Automata over AC and ACI Theories
• Flat and One-Variable Clauses for Single Blind Copying Protocols: The XOR Case
• Decidability and closure properties of equational tree languages
• Monotone AC-Tree Automata
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science

This page was built for publication: Two-way equational tree automata for AC-like theories: Decidability and closure properties

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