A useful device for showing the solvability of some decision problems

DOI10.1016/S0022-0000(76)80026-8zbMATH Open0338.68046MaRDI QIDQ1230657FDOQ1230657

Authors: 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)

Cites Work

• Parallel program schemata
• Bounded Algol-Like Languages
• On Context-Free Languages
• On Multi-Head Finite Automata
• A variant of a recursively unsolvable problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• Bounded-reversal multihead finite automata languages
• Multi-tape and multi-head pushdown automata
• A Remark on Code Sets and Context-Free Languages

Cited In (10)

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

Uses Software

• ALGOL 60

This page was built for publication: A useful device for showing the solvability of some decision problems

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