On Complexity of Two Dimensional Languages Generated by Transducers

DOI10.1007/978-3-540-70844-5_19MaRDI QIDQ3602813zbMATH OpenOpenAlexFDO

Authors Egor Dolzhenko, Nataşa Jonoska

Publication date 12 February 2009

Published in Implementation and Applications of Automata (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70844-5_19

zbMATH Keywords

entropyfinite state automata with outputlocal languagespicture languagestransducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Expressiveness and complexity of regular pure two-dimensional context-free languages
• Classes of two-dimensional languages and recognizability conditions
• A stronger recognizability condition for two-dimensional languages
• Comparing necessary conditions for recognizability of two-dimensional languages
• scientific article; zbMATH DE number 7770055
• scientific article; zbMATH DE number 7770057
• Recognition and complexity results for projection languages of two-dimensional automata
• Complexity of two-dimensional rank-reducing grammars
• On Some Classes of 2D Languages and Their Relations
• The complexity of some decision problems about two-dimensional array grammars

Cites work

• A small aperiodic set of Wang tiles
• An Introduction to Symbolic Dynamics and Coding
• Aspects of Molecular Computing
• Automorphisms of compact groups
• Finite State Automata Representing Two-Dimensional Subshifts
• From Determinism to Non-determinism in Recognizable Two-Dimensional Languages
• scientific article; zbMATH DE number 1689049 (Why is no real title available?)
• scientific article; zbMATH DE number 3114014 (Why is no real title available?)
• scientific article; zbMATH DE number 177162 (Why is no real title available?)
• scientific article; zbMATH DE number 3597901 (Why is no real title available?)
• Matrix-based complexity functions and recognizable picture languages
• Theory Is Forever
• Tiling Automaton: A Computational Model for Recognizable Two-Dimensional Languages
• TRANSITIVITY IN TWO-DIMENSIONAL LOCAL LANGUAGES DEFINED BY DOT SYSTEMS
• Unambiguous recognizable two-dimensional languages

Cited in

(8)

• Complexity of two-dimensional rank-reducing grammars
• Two-dimensional languages and cellular automata
• Two-dimensional rational automata: a bridge unifying one- and two-dimensional language theory
• On Some Classes of 2D Languages and Their Relations
• TRANSITIVITY IN TWO-DIMENSIONAL LOCAL LANGUAGES DEFINED BY DOT SYSTEMS
• From Determinism to Non-determinism in Recognizable Two-Dimensional Languages
• Non-recursive Trade-offs between Two-Dimensional Automata and Grammars
• Transducer generated arrays of robotic nano-arms

This page was built for publication: On Complexity of Two Dimensional Languages Generated by Transducers

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