Rigid tree automata and applications
From MaRDI portal
Publication:553317
DOI10.1016/j.ic.2010.11.015zbMath1217.68131OpenAlexW2094342038MaRDI QIDQ553317
Florent Jacquemard, Camille Vacher, Francis Klay
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
Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Grammars and rewriting systems (68Q42)
Related Items
The emptiness problem for tree automata with at least one global disequality constraint is NP-hard ⋮ Algorithmic introduction of quantified cuts ⋮ On the compressibility of finite languages and formal proofs ⋮ Tree Automata, (Dis-)Equality Constraints and Term Rewriting ⋮ Unnamed Item ⋮ Rigid Tree Automata ⋮ Compressibility of Finite Languages by Grammars ⋮ Inductive theorem proving based on tree grammars ⋮ Emptiness and finiteness for tree automata with global reflexive disequality constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Closure properties and decision problems of dag automata
- Deciding \(\mathcal H_1\) by resolution
- Deterministic tree pushdown automata and monadic tree rewriting systems
- Haskell overloading is DEXPTIME-complete
- Tree automata with one memory set constraints and cryptographic protocols
- Security properties: two agents are sufficient
- Automata for reduction properties solving
- Tree automata with equality constraints modulo equational theories
- Pushdown tree automata
- Protocol Verification Via Rigid/Flexible Resolution
- Visibly Tree Automata with Memory and Constraints
- Visibly Pushdown Languages and Term Rewriting
- Tree Automata with Global Constraints
- Visibly pushdown languages
- Satisfiability of a Spatial Logic with Tree Variables
- Verification of Security Protocols with a Bounded Number of Sessions Based on Resolution for Rigid Variables
- Theorem Proving via General Matings
- Equality and disequality constraints on direct subterms in tree automata
- Mobile values, new names, and secure communication
- Term Rewriting and Applications
