scientific article; zbMATH DE number 18634

DOI10.1007/BFB0029626MaRDI QIDQ3976037zbMATH OpenFDO

Authors Friedhelm Hinz

Publication date 26 June 1992

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0029626

zbMATH Keywords

chain code picture languagescontext-free languagemembership problemNP-algorithmsuperpicturethree-way picture languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

[For the entire collection see Zbl 0731.00026.] The paper presents an NP-algorithm for the membership problem of a context-free picture language. Then, special cases ( three-way picture languages and context-free picture languages closed under superpicture), where the membership problem has an efficient solution, are examined; in both cases, the deterministic algorithm runs in cubic time.

Recommendations

• Complexity and decidability for chain code picture languages
• The membership and equivalence problems for picture languages
• Membership problems for regular and context-free trace languages
• Two undecidability results for chain code picture languages
• Decision problems and regular chain code picture languages
• On the connectedness of pictures in chain code picture languages
• scientific article; zbMATH DE number 4126715
• On the Membership Problem for Visibly Pushdown Languages
• scientific article; zbMATH DE number 4001507
• Complexity and decidability for restricted classes of picture languages

Cited in

(6)

• Complexity and decidability for chain code picture languages
• The membership and equivalence problems for picture languages
• On reversal-bounded picture languages
• Retreat bounded picture languages
• Membership problems for regular and context-free trace languages
• Decision problems and regular chain code picture languages

This page was built for publication:

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