Recognizing picture languages by reductions to string languages

MaRDI QIDQ5867524zbMATH OpenFDO

Authors František Mráz, Friedrich Otto

Publication date 14 September 2022

Full work available at URL http://www.jalc.de/issues/2022/issue_27_1-3/jalc-2022-199-228.php

zbMATH Keywords

reductionpicture languagetranslucent letterfinite-state acceptor

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The membership and equivalence problems for picture languages
• Restarting automata for picture languages: a survey on recent developments
• Recognizable vs. Regular Picture Languages
• Simple picture processing based on finite automata and regular grammars
• scientific article; zbMATH DE number 871248

Cites work

• A computational model for tiling recognizable two-dimensional languages
• Comparing two-dimensional one-marker automata to sgraffito automata
• Complexity of two-dimensional patterns
• Context-sensitive string languages and recognizable picture languages
• Deterministic ordered restarting automata for picture languages
• Extended two-way ordered restarting automata for picture languages
• Fast context-free grammar parsing requires fast Boolean matrix multiplication
• Globally deterministic CD-systems of stateless R-automata with window size 1
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• If the current clique algorithms are optimal, so is Valiant's parser
• Intersection non-emptiness and hardness within polynomial time
• LR-regular grammars - an extension of LR(k) grammars
• Linear Context Free Languages
• Monotonicity of restarting automata
• Multiplying matrices faster than coppersmith-winograd
• New results on deterministic sgraffito automata
• On deterministic ordered restart-delete automata
• On deterministic ordered restart-delete automata
• On regular drawn symbolic picture languages
• One-tape, off-line Turing machine computations
• Ordered restarting automata for picture languages
• Picture languages with array rewriting rules
• Picture recognizability with automata based on Wang tiles
• Recent advances in formal languages and applications.
• Recognition and complexity results for projection languages of two-dimensional automata
• Restarting automata for picture languages: a survey on recent developments
• Scanning pictures the boustrophedon way
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• Two-dimensional Sgraffito automata
• Two-dimensional pattern matching against basic picture languages
• Two-dimensional sgraffito automata
• Two-head finite-state acceptors with translucent letters
• Using string languages to describe picture languages

Cited in

(1)

• Non-returning deterministic and nondeterministic finite automata with translucent letters

This page was built for publication: Recognizing picture languages by reductions to string languages

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