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

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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