Complexity and decidability for chain code picture languages

DOI10.1016/0304-3975(85)90041-6zbMath0565.68065OpenAlexW1967134973WikidataQ54310034 ScholiaQ54310034MaRDI QIDQ1058857

Ivan Hal Sudborough, Ermo Welzl

Publication date: 1985

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

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90041-6

zbMATH Keywords

membership problemregular languagespicture description

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (19)

On regular drawn symbolic picture languages ⋮ Retreat bounded picture languages ⋮ Efficient reductions of picture words ⋮ Unambiguous description of chain code picture languages ⋮ The membership and equivalence problems for picture languages ⋮ The finiteness of synchronous, tabled picture languages is decidable ⋮ A transformation system for generating description languages of chain code pictures ⋮ Complexity and decidability for restricted classes of picture languages ⋮ Picture iteration and picture ambiguity ⋮ Valuations of languages, with applications to fractal geometry ⋮ Chain-code pictures and collages generated by hyperedge replacement ⋮ Decision problems and regular chain code picture languages ⋮ On reversal-bounded picture languages ⋮ Adding symbolic information to picture models: definitions and properties ⋮ Two undecidability results for chain code picture languages ⋮ Leftmove-bounded picture languages ⋮ Undecidability of existential properties in picture languages ⋮ On the connectedness of pictures in chain code picture languages ⋮ Decidability of the consistency problem for regular symbolic picture description languages

Cites Work

• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Using string languages to describe picture languages
• Time and tape complexity of pushdown automaton languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity and decidability for chain code picture languages