A useful device for showing the solvability of some decision problems

DOI10.1016/S0022-0000(76)80026-8MaRDI QIDQ1230657zbMATH OpenFDO

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

• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A Remark on Code Sets and Context-Free Languages
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• A variant of a recursively unsolvable problem
• Bounded Algol-Like Languages
• Bounded-reversal multihead finite automata languages
• Multi-tape and multi-head pushdown automata
• On Context-Free Languages
• On Multi-Head Finite Automata
• Parallel program schemata

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

Describes a project that uses

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)