Language classes associated with automata over matrix groups

DOI10.1051/ITA/2018017zbMATH Open1429.68105arXiv1609.00396OpenAlexW2963259539MaRDI QIDQ5223619FDOQ5223619

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)

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.

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

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

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)

Cites Work

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

Cited In (2)

• New results on vector and homing vector automata
• Title not available (Why is that?)

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)