On the group memory complexity of extended finite automata over groups

DOI10.1016/j.jlamp.2020.100605zbMath1462.68099OpenAlexW3087200916MaRDI QIDQ2210871

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

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

finite automatonextended finite automata over groupsgroup memory complexity

Mathematics Subject Classification ID

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

Related Items (3)

Jump complexity of finite automata with translucent letters ⋮ On the Degree of Extension of Some Models Defining Non-Regular Languages ⋮ Editorial: Tribute to Anna Labella

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On groups whose word problem is solved by a counter automaton.
• Finite automata with multiplication
• Remarks on blind and partially blind one-way multicounter machines
• On the degrees of non-regularity and non-context-freeness
• Word problems recognisable by deterministic blind monoid automata
• FINITE AUTOMATA OVER FREE GROUPS
• On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids
• VALENCE GRAMMARS WITH TARGET SETS
• EXTENDED FINITE AUTOMATA AND WORD PROBLEMS
• Silent Transitions in Automata with Storage
• Extended finite automata over groups

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