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

DOI10.1016/0020-0255(93)90039-OzbMATH Open0796.68187OpenAlexW4231225572MaRDI QIDQ1803862FDOQ1803862

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

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

zbMATH Keywords

connected binary picturesfinite-state acceptors

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• 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)