Equality and disequality constraints on direct subterms in tree automata

DOI10.1007/3-540-55210-3_181zbMath1493.68183OpenAlexW160847359MaRDI QIDQ5096779

Bruno Bogaert, Sophie Tison

Publication date: 18 August 2022

Published in: STACS 92 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55210-3_181

zbMATH Keywords

nonlinearitytree automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (27)

Alternating two-way AC-tree automata ⋮ Encompassment properties and automata with constraints ⋮ Towards an efficient construction of test sets for deciding ground reducibility ⋮ The emptiness problem for tree automata with at least one global disequality constraint is NP-hard ⋮ Weighted tree automata with constraints ⋮ Logics for unordered trees with data constraints ⋮ Tree automata with equality constraints modulo equational theories ⋮ Parameter reduction and automata evaluation for grammar-compressed trees ⋮ Tree Automata with Global Constraints ⋮ Pumping, cleaning and symbolic constraints solving ⋮ Tree automata for rewrite strategies ⋮ E-generalization using grammars ⋮ Decidability of equivalence for deterministic synchronized tree automata ⋮ Unification in pseudo-linear sort theories is decidable ⋮ Closure of Tree Automata Languages under Innermost Rewriting ⋮ Rigid tree automata and applications ⋮ Multitree automata that count ⋮ Grid structures and undecidable constraint theories ⋮ Weighted tree automata with constraints ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ Unnamed Item ⋮ Decidability of equivalence for deterministic synchronized tree automata ⋮ On the equivalence problem for letter-to-letter top-down tree transducers ⋮ Projection for Büchi Tree Automata with Constraints between Siblings ⋮ Sequentiality, monadic second-order logic and tree automata. ⋮ Recognizable tree-languages and nonlinear morphisms ⋮ Emptiness and finiteness for tree automata with global reflexive disequality constraints

Cites Work

• On sufficient-completeness and related properties of term rewriting systems
• The Church-Rosser property for ground term-rewriting systems is decidable
• Equational formulae with membership constraints
• Computational aspects of an order-sorted logic with term declarations
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Equality and disequality constraints on direct subterms in tree automata