New operations and regular expressions for two-dimensional languages over one-letter alphabet

DOI10.1016/J.TCS.2005.03.031MaRDI QIDQ2484449zbMATH OpenOpenAlexFDO

Authors Marcella Anselmo, Dora Giammarresi, Maria Madonia

Publication date 1 August 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.03.031

zbMATH Keywords

Regular expressionTwo-dimensional language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Developments in Language Theory
• Recognizable vs. Regular Picture Languages
• scientific article; zbMATH DE number 871248
• Towards more expressive 2D deterministic automata
• Deterministic Two-Dimensional Languages over One-Letter Alphabet

Cites work

• A characterization of recognizable picture languages by tilings by finite sets
• A note on two-dimensional finite automata
• Developments in Language Theory
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 1206599 (Why is no real title available?)
• scientific article; zbMATH DE number 871248 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Regular expressions and context-free grammars for picture languages
• Some properties of two-dimensional on-line tessellation acceptors
• Star-free picture expressions are strictly weaker than first-order logic
• Theory is forever. Essays dedicated to Arto Salomaa on the occasion of his 70th birthday.
• Three-way automata on rectangular types over a one-letter alphabet
• Tiling Recognizable Two-Dimensional Languages
• Two-dimensional finite automata and unacceptable functions

Cited in

(12)

• Deterministic and unambiguous two-dimensional languages over one-letter alphabet
• Simple picture processing based on finite automata and regular grammars
• Two-dimensional pattern matching against local and regular-like picture languages
• Decision problems and projection languages for restricted variants of two-dimensional automata
• Degrees of restriction for two-dimensional automata
• Unambiguous recognizable two-dimensional languages
• Tiling Recognizable Two-Dimensional Languages
• Recognizable vs. Regular Picture Languages
• Deterministic Two-Dimensional Languages over One-Letter Alphabet
• Developments in Language Theory
• Picture Languages Generated by Assembling Tiles
• Concatenation operations and restricted variants of two-dimensional automata

This page was built for publication: New operations and regular expressions for two-dimensional languages over one-letter alphabet

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