Groups and NTS languages

DOI10.1016/0022-0000(87)90015-8MaRDI QIDQ580992zbMATH OpenOpenAlexFDO

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

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

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)

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

Cites work

• scientific article; zbMATH DE number 3861446 (Why is no real title available?)
• scientific article; zbMATH DE number 3872710 (Why is no real title available?)
• scientific article; zbMATH DE number 3876579 (Why is no real title available?)
• scientific article; zbMATH DE number 3880671 (Why is no real title available?)
• scientific article; zbMATH DE number 3941518 (Why is no real title available?)
• scientific article; zbMATH DE number 4036066 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 3634526 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 3381862 (Why is no real title available?)
• scientific article; zbMATH DE number 3383519 (Why is no real title available?)
• Finite and infinite cyclic extensions of free groups
• Groups Presented by Finite Two-Monadic Church-Rosser Thue Systems
• Groups and Simple Languages
• Groups, the theory of ends, and context-free languages
• NTS languages are deterministic and congruential
• On Generalized Free Products of Finite Extensions of Free Groups
• The accessibility of finitely presented groups
• Une généralisation des ensembles de Dyck

Cited in

(18)

• Groups whose word problem is a Petri net language
• 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 a subclass of context-free groups
• On the rational subsets of the free group
• 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
• Space complexity and word problems of groups
• Conjugacy languages in virtual graph products
• On a kind of Fatou property of context-free groups
• About the descriptive power of certain classes of finite string-rewriting systems
• 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)