On the group memory complexity of extended finite automata over groups

DOI10.1016/J.JLAMP.2020.100605MaRDI QIDQ2210871zbMATH OpenOpenAlexFDO

Authors Fernando Arroyo, Victor Mitrana, Andrei Păun, Mihaela Păun, Jose Ramon Sanchez Couso

Publication date 9 November 2020

Published in Journal of Logical and Algebraic Methods in Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jlamp.2020.100605

zbMATH Keywords

extended finite automata over groupsfinite automatongroup memory complexity

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Formal languages and automata (68Q45)

Recommendations

• Extended finite automata over groups
• scientific article; zbMATH DE number 1972789
• Formal Languages and Groups as Memory
• Finite automata over free groups
• EXTENDED FINITE AUTOMATA AND WORD PROBLEMS

Cites work

• EXTENDED FINITE AUTOMATA AND WORD PROBLEMS
• Extended finite automata over groups
• Finite automata over free groups
• Finite automata with multiplication
• scientific article; zbMATH DE number 3725728 (Why is no real title available?)
• scientific article; zbMATH DE number 58316 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 706263 (Why is no real title available?)
• scientific article; zbMATH DE number 1361482 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 2087231 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• On groups whose word problem is solved by a counter automaton.
• On the capabilities of grammars, automata, and transducers controlled by monoids
• On the degrees of non-regularity and non-context-freeness
• Remarks on blind and partially blind one-way multicounter machines
• Silent transitions in automata with storage
• VALENCE GRAMMARS WITH TARGET SETS
• Valences in Lindenmayer systems
• Word problems recognisable by deterministic blind monoid automata

Cited in

(5)

• Editorial: Tribute to Anna Labella
• An effective lower bound for group complexity of finite semigroups and automata
• Jump complexity of finite automata with translucent letters
• On the Degree of Extension of Some Models Defining Non-Regular Languages
• Jump complexity of deterministic finite automata with translucent letters

This page was built for publication: On the group memory complexity of extended finite automata over groups

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