Language classes associated with automata over matrix groups

DOI10.1051/ITA/2018017MaRDI QIDQ5223619zbMATH OpenOpenAlexFDO

Authors Flavio D'Alessandro, A. C. Cem Say

Publication date 18 July 2019

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.00396

zbMATH Keywords

time complexitygroup automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Algebraic theory of languages and automata (68Q70)

Abstract: We investigate the language classes recognized by group automata over matrix groups. We present a summary of the results obtained so far together with a number of new results. We look at the computational power of time-bounded group automata where the group under consideration has polynomial growth.

Recommendations

• Groups, languages and automata
• scientific article; zbMATH DE number 3915631
• A course in formal languages, automata and groups
• An automatic semigroup of languages
• Group-Type Automata
• Language-theoretic problems in certain matrix monoids
• Extended finite automata over groups
• scientific article; zbMATH DE number 3903978
• Representation of automata by groups
• Representations of group automata

Cites work

• scientific article; zbMATH DE number 3875506 (Why is no real title available?)
• scientific article; zbMATH DE number 66487 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 1544074 (Why is no real title available?)
• A Turing machine time hierarchy
• Automaticity. III: Polynomial automaticity and context-free languages
• EXTENDED FINITE AUTOMATA AND WORD PROBLEMS
• Finite automata over free groups
• Finite automata with multiplication
• Formal Languages and Groups as Memory
• ON GROUPS AND COUNTER AUTOMATA
• On groups whose word problem is solved by a counter automaton.
• Remarks on blind and partially blind one-way multicounter machines
• Semigroup automata with rational initial and terminal sets
• Silent transitions in automata with storage
• Subgroups of Direct Products of Free Groups
• \(C^*\)-algebras and finite-dimensional approximations

Cited in

(2)

• New results on vector and homing vector automata
• scientific article; zbMATH DE number 3988721 (Why is no real title available?)

This page was built for publication: Language classes associated with automata over matrix groups

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