Grid structures and undecidable constraint theories

DOI10.1016/S0304-3975(00)00032-3MaRDI QIDQ5941204zbMATH OpenOpenAlexFDO

Authors F. Seynhaeve, Sophie Tison, M. Tommasi, Ralf Treinen

Publication date 20 August 2001

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(00)00032-3

zbMATH Keywords

decidable and undecidable theoriesgrid structureset constraintsterm rewritingtree automata

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• The monadic quantifier alternation hierarchy over grids and graphs
• Axiomatizing rectangular grids with no extra non-unary relations
• Undecidability in Some Structures Related to Computation Theory
• scientific article; zbMATH DE number 1223636
• Decidability of termination of grid string rewriting rules
• A unified theory of structural tractability for constraint satisfaction problems
• An undecidable fragment of the theory of set constraints

Cites work

• An undecidable fragment of the theory of set constraints
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Decidability of systems of set constraints with negative constraints
• Equality and disequality constraints on direct subterms in tree automata
• scientific article; zbMATH DE number 3727583 (Why is no real title available?)
• scientific article; zbMATH DE number 48157 (Why is no real title available?)
• scientific article; zbMATH DE number 176754 (Why is no real title available?)
• scientific article; zbMATH DE number 1330134 (Why is no real title available?)
• scientific article; zbMATH DE number 1405621 (Why is no real title available?)
• scientific article; zbMATH DE number 965572 (Why is no real title available?)
• Monadic second order definable relations on the binary tree
• On equality up-to constraints over finite trees, context unification, and one-step rewriting
• Pumping, cleaning and symbolic constraints solving
• Set constraints and automata
• Set constraints and logic programming
• Some new decidability results on positive and negative set constraints
• Syntacticness, cycle-syntacticness and shallow theories
• The first-order theory of one step rewriting in linear noetherian systems is undecidable
• The first-order theory of one-step rewriting is undecidable
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The structure of the models of decidable monadic theories of graphs
• Undecidability of the first order theory of one-step right ground rewriting

Cited in

(6)

• An undecidable fragment of the theory of set constraints
• Set constraints and automata
• The ^2 fragment of the first-order theory of atomic set constraints is _1⁰-hard
• On rewrite constraints and context unification
• The Existential Fragment of the One-Step Parallel Rewriting Theory
• Tree tuple languages from the logic programming point of view

This page was built for publication: Grid structures and undecidable constraint theories

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