Groups, the theory of ends, and context-free languages
From MaRDI portal
Publication:792454
DOI10.1016/0022-0000(83)90003-XzbMath0537.20011MaRDI QIDQ792454
David E. Muller, Paul E. Schupp
Publication date: 1983
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Formal languages and automata (68Q45) Generators, relations, and presentations of groups (20F05) Free nonabelian groups (20E05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)
Related Items (only showing first 100 items - show all)
Geometric characterizations of virtually free groups ⋮ Specular sets ⋮ \(O_n\) is an \(n\)-MCFL ⋮ Computing presentations for subgroups of polycyclic groups and of context-free groups ⋮ On Cayley graphs of virtually free groups ⋮ WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM ⋮ Self-avoiding walks and multiple context-free languages ⋮ The theory of ends, pushdown automata, and second-order logic ⋮ Word problems of groups: formal languages, characterizations and decidability ⋮ The complexity of solution sets to equations in hyperbolic groups ⋮ The (nested) word problem ⋮ On a subclass of context-free groups ⋮ The co-word problem for the Higman-Thompson group is context-free ⋮ Context-free languages and random walks on groups ⋮ Thue systems as rewriting systems ⋮ On the parallel complexity of linear groups ⋮ The word problem of \(\mathbb{Z}^n\) is a multiple context-free language ⋮ Complexity, combinatorial group theory and the language of palutators ⋮ Inverse monoids: decidability and complexity of algebraic questions. ⋮ EXTENDED FINITE AUTOMATA AND WORD PROBLEMS ⋮ A NOTE ON THE GRAMMAR OF COMBINGS ⋮ ON GROUPS WHICH ARE SYNTACTIC MONOIDS OF DETERMINISTIC CONTEXT-FREE LANGUAGES ⋮ On the word problem for special monoids ⋮ GROUPS AND SEMIGROUPS WITH A ONE-COUNTER WORD PROBLEM ⋮ On groups whose word problem is solved by a counter automaton. ⋮ The language of self-avoiding walks ⋮ Geodesic growth in virtually abelian groups ⋮ On the rational subset problem for groups. ⋮ The isomorphism problem for finite extensions of free groups is in PSPACE ⋮ On the rational subsets of the free group ⋮ On the complexity of the cogrowth sequence ⋮ ALGORITHMIC PROBLEMS ON INVERSE MONOIDS OVER VIRTUALLY FREE GROUPS ⋮ Entropy sensitivity of languages defined by infinite automata, via Markov chains with forbidden transitions ⋮ On the word problem for free products of semigroups and monoids ⋮ Groups and Simple Languages ⋮ Graphs and groups with tree-like properties ⋮ About the descriptive power of certain classes of finite string-rewriting systems ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ Context-free pairs of groups. I: Context-free pairs and graphs ⋮ On a class of poly-context-free groups generated by automata ⋮ Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Commutativity in groups presented by finite Church-Rosser Thue systems ⋮ GROWTHS OF ENDOMORPHISMS OF FINITELY GENERATED SEMIGROUPS ⋮ Topologically trivial closed walks in directed surface graphs ⋮ Context-free pairs of groups. II: Cuts, tree sets, and random walks ⋮ An effective version of Stallings' theorem in the case of context-free groups ⋮ The complexity of Grigorchuk groups with application to cryptography ⋮ GROUPS WITH CONTEXT-FREE CONJUGACY PROBLEMS ⋮ Solutions to twisted word equations and equations in virtually free groups ⋮ Some remarks on a theorem of Sakarovitch ⋮ Multipass automata and group word problems ⋮ On a kind of Fatou property of context-free groups ⋮ Automorphism groups of context-free graphs ⋮ The large scale geometry of strongly aperiodic subshifts of finite type ⋮ Gilman's conjecture ⋮ Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems ⋮ On weakly confluent monadic string-rewriting systems ⋮ The loop problem for Rees matrix semigroups. ⋮ CONTEXT-FREE GROUPS AND THEIR STRUCTURE TREES ⋮ Group presentations, formal languages and characterizations of one- counter groups ⋮ Logical aspects of Cayley-graphs: the group case ⋮ The loop problem for monoids and semigroups ⋮ A context-free and a 1-counter geodesic language for a Baumslag-Solitar group ⋮ Space Complexity and Word Problems of Groups ⋮ On mathematical contributions of Paul E. Schupp ⋮ Unnamed Item ⋮ Groups Presented by Finite Two-Monadic Church-Rosser Thue Systems ⋮ ON GROUPS AND COUNTER AUTOMATA ⋮ Groups and NTS languages ⋮ Word problems recognisable by deterministic blind monoid automata ⋮ Real computational universality: the word problem for a class of groups with infinite presentation ⋮ The generalised word problem in hyperbolic and relatively hyperbolic groups ⋮ Formal Languages and Groups as Memory ⋮ Malcev presentations for subsemigroups of direct products of coherent groups. ⋮ DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS ⋮ Subsemigroups of groups: presentations, Malcev presentations, and automatic structures ⋮ LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE ⋮ On some variants of the Ehrenfeucht conjecture ⋮ Groups whose word problems are not semilinear ⋮ On finitely generated submonoids of virtually free groups ⋮ MULTIPLICATIVE MEASURES ON FREE GROUPS ⋮ Embeddings into Thompson's group V and coCF groups ⋮ THE IDEMPOTENT PROBLEM FOR AN INVERSE MONOID ⋮ Algorithmic properties of inverse monoids with hyperbolic and tree-like Schützenberger graphs ⋮ Groups Whose Word Problem is a Petri Net Language ⋮ Anisimov's Theorem for inverse semigroups ⋮ Free products in R. Thompson’s group 𝑉 ⋮ GROUPS WITH INDEXED CO-WORD PROBLEM ⋮ ON GROUPS PRESENTED BY MONADIC REWRITING SYSTEMS WITH GENERATORS OF FINITE ORDER ⋮ When Is a Graph Product of Groups Virtually-Free? ⋮ Non-finitely generated maximal subgroups of context-free monoids ⋮ Regular left-orders on groups ⋮ Sur les monoides à un relateur qui sont des groupes ⋮ A note on a special one-rule semi-Thue system ⋮ Asymptotic invariants, complexity of groups and related problems ⋮ GROUPS WITH CONTEXT-FREE REDUCED WORD PROBLEM ⋮ MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies ⋮ Growth and ergodicity of context-free languages
Cites Work
This page was built for publication: Groups, the theory of ends, and context-free languages
