A useful device for showing the solvability of some decision problems

DOI10.1016/S0022-0000(76)80026-8zbMath0338.68046MaRDI QIDQ1230657

Oscar H. Ibarra, Chul Eung Kim

Publication date: 1976

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25)

Related Items

Hierarchies of one-way multihead automata languages, Complexity of multi-head finite automata: origins and directions, On the Density of Context-Free and Counter Languages, 2DST mappings of languages and related problems, More decidable instances of Post's correspondence problem: beyond counting, A NOTE ON REBOUND TURING MACHINES, One-way simple multihead finite automata, Some classes of languages in \(NC^ 1\), One-way simple multihead finite automata are not closed under concatenation, Alternating simple multihead finite automata

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• Parallel program schemata
• A Remark on Code Sets and Context-Free Languages
• Bounded-reversal multihead finite automata languages
• Bounded Algol-Like Languages
• On Context-Free Languages
• On Multi-Head Finite Automata
• Multi-tape and multi-head pushdown automata
• A variant of a recursively unsolvable problem