Grid structures and undecidable constraint theories
From MaRDI portal
Publication:5941204
DOI10.1016/S0304-3975(00)00032-3zbMath0973.68097OpenAlexW2039226338MaRDI QIDQ5941204
F. Seynhaeve, Sophie Tison, Ralf Treinen, Marc Tommasi
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
Related Items
Tree tuple languages from the logic programming point of view, The Existential Fragment of the One-Step Parallel Rewriting Theory, An undecidable fragment of the theory of set constraints, Set constraints and automata, The \(\exists\forall^2\) fragment of the first-order theory of atomic set constraints is \(\Pi_1^0\)-hard, On rewrite constraints and context unification
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The structure of the models of decidable monadic theories of graphs
- Set constraints and logic programming
- An undecidable fragment of the theory of set constraints
- Set constraints and automata
- Syntacticness, cycle-syntacticness and shallow theories
- Decidability of systems of set constraints with negative constraints
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Monadic second order definable relations on the binary tree
- Undecidability of the first order theory of one-step right ground rewriting
- The first-order theory of one step rewriting in linear noetherian systems is undecidable
- Pumping, cleaning and symbolic constraints solving
- The first-order theory of one-step rewriting is undecidable
- Some new decidability results on positive and negative set constraints
- Equality and disequality constraints on direct subterms in tree automata
- On equality up-to constraints over finite trees, context unification, and one-step rewriting
- Decidability of Second-Order Theories and Automata on Infinite Trees
