Rigid tree automata and applications

DOI10.1016/J.IC.2010.11.015MaRDI QIDQ553317zbMATH OpenOpenAlexFDO

Authors Florent Jacquemard, Francis Klay, Camille Vacher

Publication date 27 July 2011

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2010.11.015

zbMATH Keywords

symbol constraintsterm rewritingtree automataverification

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Rigid Tree Automata
• Tree Automata with Equality Constraints Modulo Equational Theories
• Tree automata with equality constraints modulo equational theories
• scientific article; zbMATH DE number 2040904
• Tree Automata with Memory, Visibility and Structural Constraints

Cites work

• Automata for reduction properties solving
• Closure properties and decision problems of dag automata
• Deciding H₁ by resolution
• Deterministic tree pushdown automata and monadic tree rewriting systems
• Equality and disequality constraints on direct subterms in tree automata
• Haskell overloading is DEXPTIME-complete
• scientific article; zbMATH DE number 1614701 (Why is no real title available?)
• scientific article; zbMATH DE number 1927582 (Why is no real title available?)
• Mobile values, new names, and secure communication
• Protocol Verification Via Rigid/Flexible Resolution
• Pushdown tree automata
• Satisfiability of a Spatial Logic with Tree Variables
• Security properties: two agents are sufficient
• Term Rewriting and Applications
• Theorem Proving via General Matings
• Tree automata with equality constraints modulo equational theories
• Tree Automata with Global Constraints
• Tree automata with one memory set constraints and cryptographic protocols
• Verification of Security Protocols with a Bounded Number of Sessions Based on Resolution for Rigid Variables
• Visibly pushdown languages
• Visibly Pushdown Languages and Term Rewriting
• Visibly Tree Automata with Memory and Constraints

Cited in

(13)

• On the compressibility of finite languages and formal proofs
• Inductive theorem proving based on tree grammars
• Emptiness and finiteness for tree automata with global reflexive disequality constraints
• Tree automata, (dis-)equality constraints and term rewriting. What's new?
• The emptiness problem for tree automata with at least one global disequality constraint is NP-hard
• Rigid Tree Automata
• Algorithmic introduction of quantified cuts
• scientific article; zbMATH DE number 2040904 (Why is no real title available?)
• scientific article; zbMATH DE number 1754629 (Why is no real title available?)
• Tree automata with global constraints for infinite trees
• An Automata Theoretic Approach to Rational Tree Relations
• Compressibility of Finite Languages by Grammars
• Tree Automata with Memory, Visibility and Structural Constraints

This page was built for publication: Rigid tree automata and applications

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