On the capabilities of grammars, automata, and transducers controlled by monoids
Pages 222 - 233
Abstract
During recent decades, classical models in language theory have been extended by control mechanisms defined by monoids. We study which monoids cause the extensions of context-free grammars, finite automata, or finite state transducers to exceed the capacity of the original model. Furthermore, we investigate when, in the extended automata model, the nondeterministic variant differs from the deterministic one in capacity. We show that all these conditions are in fact equivalent and present an algebraic characterization. In particular, the open question of whether every language generated by a valence grammar over a finite monoid is context-free is provided with a positive answer.
References
[1]
Clifford, A.H., Preston, G.B.: The Algebraic Theory of Semigroups, vol. 1. American Mathematical Society, Providence (1961).
[2]
Dassow, J., Turaev, S.: Petri net controlled grammars: the power of labeling and final markings. Romanian Journal of Information Science and Technology 12(2), 191-207 (2009).
[3]
Fernau, H., Stiebe, R.: Valence grammars with target sets. In: Words, Semigroups, and Transductions. World Scientific, Singapore (2001).
[4]
Fernau, H., Stiebe, R.: Sequential grammars and automata with valences. Theoretical Computer Science 276, 377-405 (2002).
[5]
Greibach, S.A.: Remarks on blind and partially blind one-way multicounter machines. Theoretical Computer Science 7(3), 311-324 (1978).
[6]
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (1979).
[7]
Ito, M., Martín-Vide, C., Mitrana, V.: Group weighted finite transducers. Acta Informatica 38, 117-129 (2001).
[8]
Kambites, M.: Formal languages and groups as memory. Communications in Algebra 37, 193-208 (2009).
[9]
Mitrana, V., Stiebe, R.: Extended finite automata over groups. Discrete Applied Mathematics 108(3), 287-300 (2001).
[10]
Ogden, W.: A helpful result for proving inherent ambiguity. Mathematical Systems Theory 2(3), 191-194 (1968).
[11]
Paun, G.: A new generative device: Valence grammars. Revue Roumaine de Mathématiques Pures et Appliquées 25, 911-924 (1980).
[12]
Render, E.: Rational Monoid and Semigroup Automata. PhD thesis, University of Manchester (2010).
[13]
Render, E., Kambites, M.: Rational subsets of polycyclic monoids and valence automata. Information and Computation 207(11), 1329-1339 (2009).
[14]
Render, E., Kambites, M.: Semigroup automata with rational initial and terminal sets. Theoretical Computer Science 411(7-9), 1004-1012 (2010).
- On the capabilities of grammars, automata, and transducers controlled by monoids
Recommendations
Visibly Pushdown Automata and Transducers with Counters
Non-Classical Models of Automata and Applications VIWe generalize the models of visibly pushdown automata (VPDAs) and visibly pushdown transducers (VPDTs) by equipping them with reversal-bounded counters. We show that some of the results for VPDAs and VPDTs (e.g., closure under intersection and ...
Two-Way Visibly Pushdown Automata and Transducers
LICS '16: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer ScienceAutomata-logic connections are pillars of the theory of regular languages. Such connections are harder to obtain for transducers, but important results have been obtained recently for word-to-word transformations, showing that the three following models ...
Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
We investigate the conversion of one-way nondeterministic finite automata and context-free grammars into Parikh equivalent one-way and two-way deterministic finite automata, from a descriptional complexity point of view. We prove that for each one-way ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 04 July 2011
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Nov 2024