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

entropytransducerspicture languageslocal languagesfinite state automata with output

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

• 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?)
• 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
• Matrix-based complexity functions and recognizable picture languages
• TRANSITIVITY IN TWO-DIMENSIONAL LOCAL LANGUAGES DEFINED BY DOT SYSTEMS
• Theory Is Forever
• Tiling Automaton: A Computational Model for Recognizable Two-Dimensional Languages
• Unambiguous recognizable two-dimensional languages

Cited in

(8)

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

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)