A Survey on Picture-Walking Automata

DOI10.1007/978-3-642-24897-9_9zbMath1350.68174OpenAlexW149984445WikidataQ62045924 ScholiaQ62045924MaRDI QIDQ3098039

Jarkko Peltomäki, Jarkko Kari

Publication date: 11 November 2011

Published in: Algebraic Foundations in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-24897-9_9

zbMATH Keywords

picture languages2-dimensional automatapicture-walking automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Concatenation operations and restricted variants of two-dimensional automata ⋮ Non-expandable non-overlapping sets of pictures ⋮ Problems on finite automata and the exponential time hypothesis ⋮ Unbordered Pictures: Properties and Construction ⋮ Characterization and measure of infinite two-dimensional strong prefix codes ⋮ Reversibility of computations in graph-walking automata ⋮ Simple picture processing based on finite automata and regular grammars ⋮ Decision problems and projection languages for restricted variants of two-dimensional automata ⋮ Sets of Pictures Avoiding Overlaps ⋮ Plane-Walking Automata ⋮ Membership Problem for Two-Dimensional General Row Jumping Finite Automata ⋮ Two-dimensional codes ⋮ Degrees of restriction for two-dimensional automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two-dimensional alternative Turing machines
• Three-way automata on rectangular types over a one-letter alphabet
• A note on three-way two dimensional alternating Turing machines
• Halting space-bounded computations
• Three-way tape-bounded two-dimensional Turing machines
• A note on decision problems for three-way two-dimensional finite automata
• Some remarks on two-dimensional finite automata
• Complexity of two-dimensional patterns
• A note on two-dimensional probabilistic finite automata
• Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\(\circ\)-rotation
• A survey of two-dimensional automata theory
• Two-dimensional alternating turing machines with only universal states
• Alternating Pushdown and Stack Automata
• On Context-Free Languages
• Theory Is Forever

This page was built for publication: A Survey on Picture-Walking Automata