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)

Full work available at URL https://doi.org/10.1016/S0022-0000(76)80026-8

Mathematics Subject Classification ID

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

Cites work

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

Cited in

(10)

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

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)