Formal Languages and Groups as Memory
From MaRDI portal
Abstract: We present an exposition of the theory of finite automata augmented with a multiply-only register storing an element of a given monoid or group. Included are a number of new results of a foundational nature. We illustrate our techniques with a group-theoretic interpretation and proof of a key theorem of Chomsky and Schutzenberger from formal language theory.
Recommendations
- scientific article; zbMATH DE number 1283959
- scientific article; zbMATH DE number 848082
- scientific article; zbMATH DE number 3887910
- Formal languages, word problems of groups and decidability
- Groups, languages and automata
- scientific article; zbMATH DE number 2100522
- The complexity of verbal languages over groups
- The complexity of verbal languages over groups
- Languages associated with saturated formations of groups
- Group theory and computational linguistics
Cites work
- scientific article; zbMATH DE number 5155118 (Why is no real title available?)
- scientific article; zbMATH DE number 3660804 (Why is no real title available?)
- scientific article; zbMATH DE number 3563392 (Why is no real title available?)
- scientific article; zbMATH DE number 3574107 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- EXTENDED FINITE AUTOMATA AND WORD PROBLEMS
- Extended finite automata over groups
- Finite automata with multiplication
- Groups, the theory of ends, and context-free languages
- On groups whose word problem is solved by a counter automaton.
- On the rational subset problem for groups.
- Remarks on blind and partially blind one-way multicounter machines
- Sequential grammars and automata with valences
- The accessibility of finitely presented groups
- Word problems recognisable by deterministic blind monoid automata
Cited in
(35)- Language classes associated with automata over matrix groups
- Rational subsets of polycyclic monoids and valence automata
- scientific article; zbMATH DE number 1972789 (Why is no real title available?)
- Counter machines and crystallographic structures
- The monoid of queue actions
- scientific article; zbMATH DE number 848082 (Why is no real title available?)
- C-graph automatic groups.
- Rational, recognizable, and aperiodic sets in the partially lossy queue monoid
- Context-sensitive languages and G-automata
- New results on vector and homing vector automata
- Knapsack in graph groups
- The algebraic theory of Parikh automata
- scientific article; zbMATH DE number 2100522 (Why is no real title available?)
- A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
- Languages accepted by weighted restarting automata
- Automata with counters that recognize word problems of free products
- A course in formal languages, automata and groups
- Semigroup automata with rational initial and terminal sets
- Homing vector automata
- The emptiness problem for valence automata over graph monoids
- On the group memory complexity of extended finite automata over groups
- scientific article; zbMATH DE number 7561314 (Why is no real title available?)
- On strong affine representations of the polycyclic monoids
- Weighted automata with storage
- Groups whose word problems are accepted by abelian G-automata
- Rational weighted tree languages with storage
- The transformation monoid of a partially lossy queue
- Principal abstract families of weighted tree languages
- The inclusion structure of partially lossy queue monoids and their trace submonoids
- Polycyclic and Bicyclic Valence Automata
- The theory of reachability of trace-pushdown systems
- Reachability in trace-pushdown systems
- Recent advances on reachability problems for valence systems (invited talk)
- On the capabilities of grammars, automata, and transducers controlled by monoids
- Group Input Machine
This page was built for publication: Formal Languages and Groups as Memory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3618533)
