English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

It turns out that there exists a surprising connection between certain ideas from the areas listed in the title. In this announcement we try to briefly outline the connection and to state our principal results. Very roughly, we use concepts from formal language theory, group theory, and the theory of ends to investigate a class of graphs which we call context-free graphs. Using the results obtained and Rabin's theorem on the decidability of the monadic second-order theory of the infinite binary tree, we show that the monadic theory of any context-free graph is decidable. There are several classes of extensively investigated decision problems which are essentially problems on the grid of integer lattice points in n dimensions. We here have in mind various questions concerning tiling problems, cellular auto­ mata, and vector addition systems. Most of these problems are known to be un- solvable in the classical case. We show that these problems all make sense on a very general class of graphs and are all solvable on any context-free graph. A finitely generated group can be described by a presentation G = (X; R) in terms of generators and defining relators. (All groups and presentations which we mention are assumed to be finitely generated.) The word problem of G is the set W(G) of all words on the generators and their inverses which represent the identity element of G. Anisimov (1) raised the question: "If W(G) is a context-free language in the sense of formal language theory, what can one say about the alge­ braic structure of GV9 We were led to conjecture that G has context-free word problem if and only if G has a free subgroup of finite index, and we have essen­ tially proven the conjecture. Our main tool is the theory of ends. Let T be the Cayley graph of a finitely-generated group G — <X;R). Let T^ denote the subgraph of T consist­ ing of all vertices and edges connected to the identity by a path of length less than n. The number of ends of G is the limit as n goes to infinity of the number of infinite components of rV^. Stallings (4) proved that a group with more than one end has a particular structure in terms of certain group-theoretic con­ structions. We prove that an infinite group with context-free word problem has

Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems