Groups and NTS languages

DOI10.1016/0022-0000(87)90015-8zbMATH Open0626.68056OpenAlexW1963661582MaRDI QIDQ580992FDOQ580992

Géraud Sénizergues, Jean-Michel Autebert, Luc Boasson

Publication date: 1987

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(87)90015-8

Recommendations

• Context-Free Groups and Bass–Serre Theory
• Groups, the theory of ends, and context-free languages
• On a subclass of context-free groups
• On a kind of Fatou property of context-free groups
• The word problem of \(\mathbb{Z}^n\) is a multiple context-free language

zbMATH Keywords

cylindercombinatorial propertyvirtually free groupscontext-free groupsgroup languagesNTS languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free nonabelian groups (20E05) Generators, relations, and presentations of groups (20F05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Finite and infinite cyclic extensions of free groups
• The accessibility of finitely presented groups
• Groups, the theory of ends, and context-free languages
• Groups and Simple Languages
• Title not available (Why is that?)
• NTS languages are deterministic and congruential
• Une généralisation des ensembles de Dyck
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Groups Presented by Finite Two-Monadic Church-Rosser Thue Systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Generalized Free Products of Finite Extensions of Free Groups
• Title not available (Why is that?)

Cited In (18)

• Space Complexity and Word Problems of Groups
• Groups, languages and dendric shifts
• A note on regular classes in special Thue systems
• On weakly confluent monadic string-rewriting systems
• Some remarks on a theorem of Sakarovitch
• Gilman's conjecture
• On the rational subsets of the free group
• On a subclass of context-free groups
• Complexity, combinatorial group theory and the language of palutators
• An effective version of Stallings' theorem in the case of context-free groups
• Computing presentations for subgroups of polycyclic groups and of context-free groups
• Group presentations, formal languages and characterizations of one- counter groups
• Conjugacy languages in virtual graph products
• About the descriptive power of certain classes of finite string-rewriting systems
• On a kind of Fatou property of context-free groups
• Groups Whose Word Problem is a Petri Net Language
• When Is a Graph Product of Groups Virtually-Free?
• Word problems of groups: formal languages, characterizations and decidability

This page was built for publication: Groups and NTS languages

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