Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 6 / Issue 9

available in:   PDF (180 kB) PS (66 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-006-09-0850


Uniquely Parsable Accepting Grammar Systems

Carlos Martín-Vide (Research Group on Mathematical Linguistics, Rovira i Virgili University, Spain)

Victor Mitrana (University of Bucharest, Faculty of Mathematics, Romania)

Abstract: We extend the restrictions which induce unique parsability in Chomsky grammars to accepting grammar systems. It is shown that the accepting power of global RC-uniquely parsable accepting grammar systems equals the computational power of deterministic pushdown automata. More computational power, keeping the parsability without backtracking, is observed for local accepting grammar systems satisfying the prefix condition. We discuss a simple recognition algorithm for these systems.

Categories: F.4.2, F.4.3