Back to Search
Start Over
Decidable First-Order Theories of One-Step Rewriting in Trace Monoids.
- Source :
-
Theory of Computing Systems . Jan/Feb2005, Vol. 38 Issue 1, p39-81. 43p. - Publication Year :
- 2005
-
Abstract
- We prove that the first-order theory of the one-step rewriting relation associated with a trace rewriting system is decidable but in general not elementary. This extends known results on semi-Thue systems but our proofs use new methods; these new methods yield the decidability of local properties expressed in first-order logic augmented by modulo-counting quantifiers. Using the main decidability result, we define several subclasses of trace rewriting systems for which the confluence problem is decidable. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 14324350
- Volume :
- 38
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Theory of Computing Systems
- Publication Type :
- Academic Journal
- Accession number :
- 15520542
- Full Text :
- https://doi.org/10.1007/s00224-004-1099-9