Two-dimensional connected pictures are not recognizable by finite-state acceptors

DOI10.1016/0020-0255(93)90039-OMaRDI QIDQ1803862zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 29 June 1993

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0255(93)90039-o

zbMATH Keywords

connected binary picturesfinite-state acceptors

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computing methodologies for image processing (68U10)

Recommendations

• Three-dimensional connected pictures are not recognizable by finite-state acceptors
• scientific article; zbMATH DE number 871248
• On the connectedness of pictures in chain code picture languages
• Two undecidability results for chain code picture languages
• A stronger recognizability condition for two-dimensional languages
• Implementation and Application of Automata
• Classes of two-dimensional languages and recognizability conditions
• scientific article; zbMATH DE number 871244
• Some remarks on two-dimensional finite automata
• Comparing necessary conditions for recognizability of two-dimensional languages

Cites work

• scientific article; zbMATH DE number 3738961 (Why is no real title available?)
• Some properties of two-dimensional on-line tessellation acceptors
• Three-dimensional connected pictures are not recognizable by finite-state acceptors

Cited in

(4)

• (Un)decidability of the emptiness problem for multi-dimensional context-free grammars
• Non-recursive trade-offs between two-dimensional automata and grammars
• Connectedness of coherent fuzzy pictures
• Three-dimensional connected pictures are not recognizable by finite-state acceptors

This page was built for publication: Two-dimensional connected pictures are not recognizable by finite-state acceptors

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