On the regular structure of prefix rewriting

DOI10.1016/0304-3975(92)90278-NzbMath0780.68077MaRDI QIDQ685354

Didier Caucal

Publication date: 6 February 1994

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

zbMATH Keywords

regular graphlabelled word rewriting systemprefix transition graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)

Related Items (36)

On rationally controlled one-rule insertion systems ⋮ Model Checking Procedural Programs ⋮ Intruder deduction for the equational theory of abelian groups with distributive encryption ⋮ Regular model checking: evolution and perspectives ⋮ Infinite results ⋮ Bisimulation collapse and the process taxonomy ⋮ Properties and limits of recognition of sets of integers by countable automata ⋮ Unnamed Item ⋮ Selected Ideas Used for Decidability and Undecidability of Bisimilarity ⋮ An efficient automata approach to some problems on context-free grammars. ⋮ Decidability of bisimulation equivalence for normed pushdown processes ⋮ On complexity functions of infinite words associated with generalized Dyck languages ⋮ Rewrite Systems with Constraints ⋮ Complexity results for prefix grammars ⋮ The modular decomposition of countable graphs. Definition and construction in monadic second-order logic ⋮ Petri nets are less expressive than state-extended PA ⋮ Reachability Analysis of Pushdown Systems with an Upper Stack ⋮ On the computational complexity of bisimulation, redux ⋮ Logical aspects of Cayley-graphs: the group case ⋮ Computing by commuting. ⋮ Pushdown automata, multiset automata, and Petri nets ⋮ Decidability of model checking with the temporal logic EF ⋮ Deciding bisimulation-like equivalences with finite-state processes ⋮ On the Petri net realization of context-free graphs ⋮ The regular viewpoint on PA-processes ⋮ Interprocedural Analysis of Concurrent Programs Under a Context Bound ⋮ Reachability is decidable for weakly extended process rewrite systems ⋮ The Reachability Problem over Infinite Graphs ⋮ Decidability of bisimulation equivalence for normed pushdown processes ⋮ Context-free event domains are recognizable ⋮ On the complexity of a family of \(k\)-context-free sequences ⋮ Context-free event domains are recognizable ⋮ On the symbolic reduction of processes with cryptographic functions. ⋮ Process rewrite systems. ⋮ Simulation preorder over simple process algebras ⋮ Reflections on a Geometry of Processes

Cites Work

• Hyperedge replacement: grammars and languages
• The theory of ends, pushdown automata, and second-order logic
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• Regular canonical systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the regular structure of prefix rewriting