Minimization and Characterizations for Biautomata

• Autorzy: Holzer M. , Jakobi S.

Identyfikatory

DOI

10.3233/FI-2015-1146

• Języki publikacji: EN

Abstrakty

EN

We show how to minimize biautomata with adaptations of classical minimization algorithms for ordinary deterministic finite automata and moreover by a Brzozowski-like minimization algorithm by applying reversal and power-set construction twice to the biautomaton under consideration. Biautomata were recently introduced in [O. KL´I MA, L. POL´A K: On biautomata. RAIRO— Theor. Inf. Appl., 46(4), 2012] as a generalization of ordinary finite automata, reading the input from both sides. The correctness of the Brzozowski-like minimization algorithm needs a little bit more argumentation than for ordinary finite automata since for a biautomaton its dual or reverse automaton, built by reversing all transitions, does not necessarily accept the reversal of the original language. To this end we first use the recently introduced notion of nondeterminism for biautomata [M. HOLZER, S. JAKOBI: Nondeterministic Biautomata and Their Descriptional Complexity. In: 15th DCFS, Number 8031 of LNCS, 2013] and take structural properties of the forward- and backward-transitions of the automaton into account. This results in a variety of biautomata models, the accepting power of which is characterized. As a byproduct we give a simple structural characterization of cyclic regular and commutative regular languages in terms of deterministic biautomata.

Słowa kluczowe

EN

nondeterministic biautomata; structural properties; minimization; commutative language; cyclic languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 136, nr 1/2
• Strony: 113--137
• Opis fizyczny: Bibliogr. 11 poz., rys.

Twórcy

autor

Holzer M.

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

autor

Jakobi S.

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

Bibliografia

• [1] Brzozowski, J. A.: Canonical Regular Expressions and Minimal State Graphs for Definite Events, in: Mathematical Theory of Automata, vol. 12 of MRI Symposia Series, Polytechnic Press, Brooklyn, NY, 1962, 529–561.
• [2] Brzozowski, J. A.: Derivatives of regular expressions, J. ACM, 11, 1964, 481–494.
• [3] Champarnaud, J.-M., Dubernard, J.-P., Jeanne, H., Mignot, L.: Two-Sided Derivatives for Regular Expressions and for Hairpin Expressions, Proceedings of the 7th International Conference on Language and Automata Theory and Applications (A.-H. Dediu, C. Martín-Vide, B. Truthe, Eds.), number 7810 in LNCS, Springer, Bilbao, Spain, 2013.
• [4] Hartmanis, J.: On the Succinctness of Different Representations of Languages, SIAM J. Comput., 9(1), 1980, 114–120.
• [5] Holzer,M., Jakobi, S.: Nondeterministic Biautomata and Their Descriptional Complexity, Proceedings of the 15th International Workshop on Descriptional Complexity of Formal Systems (H. Jürgensen, R. Reis, Eds.), number 8031 in LNCS, Springer, London, Ontario, Canada, 2013.
• [6] Jirásková, G., Klíma, O.: Descriptional Complexity of Biautomata, Proceedings of the 14th International Workshop Descriptional Complexity of Formal Systems (M. Kutrib, N. Moreira, R. Reis, Eds.), number 7386 in LNCS, Springer, Braga, Portugal, 2012.
• [7] Klíma, O., Polák, L.: On Biautomata, RAIRO–Informatique théorique et Applications / Theoretical Informatics and Applications, 46(4), 2012, 573–592.
• [8] Loukanova,R.: Linear Context Free Languages, Proceedings of the 4th International Colloquium Theoretical Aspects of Computing (C. B. Jones, Z. Liu, J. Woodcock, Eds.), number 4711 in LNCS, Springer, Macau, China, 2007.
• [9] Mirkin, B. G.: On Dual Automata, Kibernetika, 2(1), 1966, 7–10.
• [10] Pin, J.-E.: Handbook of Formal Languages, Vol. 1, Word, Language, Grammar, vol. 1, chapter Syntactic Semigroups, Springer, 1997, 679–746.
• [11] Rosenberg, A. L.: A Machine Realization of the Linear Context-Free Languages, Inform. Control, 10, 1967, 175–188.