Linearly bounded infinite graphs

DOI10.1007/S00236-006-0022-ZzbMath1102.68056arXiv0705.3487OpenAlexW3102239021MaRDI QIDQ852011

Antoine Meyer, Arnaud Carayol

Publication date: 27 November 2006

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0705.3487

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (1)

An Infinite Automaton Characterization of Double Exponential Time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Synchronized rational relations of finite and infinite words
• The theory of ends, pushdown automata, and second-order logic
• The method of forced enumeration for nondeterministic automata
• Decidability of bisimulation equivalence for normed pushdown processes
• On the transition graphs of Turing machines.
• On infinite transition graphs having a decidable monadic theory
• Decomposing a $k$-valued transducer into $k$ unambiguous ones
• On certain formal properties of grammars
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• Nondeterministic Space is Closed under Complementation
• Context-Sensitive Languages, Rational Graphs and Determinism
• On Relations Defined by Generalized Finite Automata
• Classes of languages and linear-bounded automata
• An internal presentation of regular graphs by prefix-recognizable graphs

This page was built for publication: Linearly bounded infinite graphs