Finite automata with multiplication

DOI10.1016/0304-3975(76)90081-5zbMath0345.68029OpenAlexW1989780614MaRDI QIDQ1233317

Sartaj K. Sahni, Oscar H. Ibarra, Chul Eung Kim

Publication date: 1976

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(76)90081-5

Mathematics Subject Classification ID

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

Related Items

Simple counter machines and number-theoretic problems, Jump complexity of finite automata with translucent letters, Recent advances on reachability problems for valence systems (invited talk), Homing vector automata, Unnamed Item, On the group memory complexity of extended finite automata over groups, Two-way deterministic multi-weak-counter machines, FINITE AUTOMATA OVER FREE GROUPS, Extended finite automata over groups, Finite automata with multiplication, GENERALIZED COUNTERS AND REVERSAL COMPLEXITY, Word problems recognisable by deterministic blind monoid automata, New Results on Vector and Homing Vector Automata, Formal Languages and Groups as Memory, One-way simple multihead finite automata, On the sentence valuation in a semiring, Language classes associated with automata over matrix groups, One-way simple multihead finite automata are not closed under concatenation, Alternating simple multihead finite automata, Sequential grammars and automata with valences

Uses Software

• ALGOL 60

Cites Work

• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• Finite automata with multiplication
• Note on analogue memory automata
• Multitape one-way nonwriting automata
• Parallel program schemata
• Bounded-reversal multihead finite automata languages
• Bounded Algol-Like Languages
• Deterministic context free languages
• One-way stack automata
• Multi-tape and multi-head pushdown automata
• On the closure of AFL under reversal
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item