𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Undecidability Of Some Domino Connectability Problems

✍ Scribed by H.-D. Ebbinghaus

Publisher
John Wiley and Sons
Year
1982
Tongue
English
Weight
186 KB
Volume
28
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

What makes some language theory problems
What makes some language theory problems undecidable
✍ J. Hartmanis; J.E. Hopcroft πŸ“‚ Article πŸ“… 1970 πŸ› Elsevier Science 🌐 English βš– 487 KB

In the theory of automata and formal languages, the undecidability of various properties has been studied for specific classes of languages. Here we abstract the essence of various proofs of undecidability and find wide classes of properties and general conditions on families of languages such that

The undecidability of some equivalence p
The undecidability of some equivalence problems concerning ngsm's and finite substitutions
✍ P. Turakainen πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 437 KB

It is shown to be undecidable whether an c-free finite substitution and a two-state simple E-free ngsm are equivalent on {a, b}\*. Consequently, the state-minimization of such ngsm's and the nonterminal-minimization of linear grammars having two nonterminals are undecidable. Applications to some ot

Some undecidable problems involving the
Some undecidable problems involving the edge-coloring and vertex-coloring of graphs
✍ Stefan A. Burr πŸ“‚ Article πŸ“… 1984 πŸ› Elsevier Science 🌐 English βš– 477 KB

Certain problems involving the coloring the edges or vertices of infinite graphs are shown to be undecidable. In particular, let G and H be finite 3-connected graphs, or triangles. Then a doubly-periodic infinite graph F is constructed such that the following problem is undecidable: For a coloring o