scientific article; zbMATH DE number 176754

MaRDI QIDQ4036584zbMATH OpenFDO

Authors Wolfgang Thomas

Publication date 18 May 1993

zbMATH Keywords

decidable monadic second-order theoryfinite automatagraph acceptorinfinite graphstreeswords

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Recommendations

• Some notes on graph automata, tiling systems and partition logic
• Words, automata and Lie theory for tilings
• From logic to tiling
• Tiling problems, automata, and tiling graphs
• Logic, semigroups and automata on words
• scientific article; zbMATH DE number 7357521
• scientific article; zbMATH DE number 3189696
• The logic of Turing progressions
• scientific article; zbMATH DE number 3972842
• scientific article; zbMATH DE number 459361

Cited in

(26)

• Some notes on graph automata, tiling systems and partition logic
• Recognizable picture languages and domino tiling
• Expressive power of existential first-order sentences of Büchi's sequential calculus
• Uniform and nonuniform recognizability.
• Reversibility of computations in graph-walking automata
• Generalising automaticity to modal properties of finite structures
• Recognizable series on graphs and hypergraphs
• Message-passing automata are expressively equivalent to EMSO logic
• Computability by monadic second-order logic
• A Nivat theorem for weighted picture automata and weighted MSO logic
• Weighted automata and logics on infinite graphs
• Words, automata and Lie theory for tilings
• A logical approach to locality in pictures languages
• A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
• Unambiguous recognizable two-dimensional languages
• Subshifts, Languages and Logic
• Subshifts as models for MSO logic
• On the Ehrenfeucht-Fraïssé game in theoretical computer science (extended abstract)
• Asynchronous cellular automata for infinite traces
• Grid structures and undecidable constraint theories
• Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs
• The monadic second-order logic of graphs. IX: Machines and their behaviours
• Weighted tiling systems for graphs: evaluation complexity
• FO logic on cellular automata orbits equals MSO logic
• Existential MSO over two successors is strictly weaker than over linear orders
• Definable transductions and weighted logics for texts

This page was built for publication:

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