From \(\omega\)-regular expressions to Büchi automata via partial derivatives. (English) Zbl 1451.68162
Dediu, Adrian-Horia (ed.) et al., Language and automata theory and applications. 9th international conference, LATA 2015, Nice, France, March 2–6, 2015. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8977, 287-298 (2015).
Summary: We extend Brzozowski derivatives and partial derivatives from regular expressions to \(\omega\)-regular expressions and establish their basic properties. We observe that the existing derivative-based automaton constructions do not scale to \(\omega\)-regular expressions. We define a new variant of the partial derivative that operates on linear factors and prove that this variant gives rise to a translation from \(\omega\)-regular expressions to nondeterministic Büchi automata.
For the entire collection see [Zbl 1331.68009].
For the entire collection see [Zbl 1331.68009].
MSC:
| 68Q45 | Formal languages and automata |
References:
| [1] | Antimirov, VM; Reichel, H., Rewriting regular inequalities, FCT 1995, 116-125 (1995), Heidelberg: Springer, Heidelberg · Zbl 1507.68164 |
| [2] | Antimirov, VM, Partial derivatives of regular expressions and finite automaton constructions, Theoretical Computer Science, 155, 2, 291-319 (1996) · Zbl 0872.68120 · doi:10.1016/0304-3975(95)00182-4 |
| [3] | Brzozowski, JA, Derivatives of regular expressions, J. ACM, 11, 4, 481-494 (1964) · Zbl 0225.94044 · doi:10.1145/321239.321249 |
| [4] | Caron, P.; Champarnaud, J-M; Mignot, L.; Dediu, A-H; Inenaga, S.; Martín-Vide, C., Partial derivatives of an extended regular expression, Language and Automata Theory and Applications, 179-191 (2011), Heidelberg: Springer, Heidelberg · Zbl 1330.68148 · doi:10.1007/978-3-642-21254-3_13 |
| [5] | Kleene, S.C.: Representation of events in nerve nets and finite automata. Automata Studies (1956) |
| [6] | Park, D.; Deussen, P., Concurrency and automata on infinite sequences, Theoretical Computer Science, 167-183 (2003), Heidelberg: Springer, Heidelberg · Zbl 0457.68049 · doi:10.1007/BFb0017309 |
| [7] | Redziejowski, RR, Construction of a deterministic \(\omega \)-automaton using derivatives, Informatique Théorique et Applications, 33, 2, 133-158 (1999) · Zbl 0946.68078 · doi:10.1051/ita:1999111 |
| [8] | Redziejowski, RR, An improved construction of deterministic omega-automaton using derivatives, Fundam. Inform., 119, 3-4, 393-406 (2012) · Zbl 1279.68173 |
| [9] | Roşu, G.; Viswanathan, M.; Nieuwenhuis, R., Testing extended regular language membership incrementally by rewritin, Rewriting Techniques and Applications, 499-514 (2003), Heidelberg: Springer, Heidelberg · Zbl 1038.68562 · doi:10.1007/3-540-44881-0_35 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
