ResearchSpace
The state complexity of language operations on XNFA-succinct unary regular languages
JavaScript is disabled for your browser. Some features of this site may not work without it.
- ResearchSpace
- →
- CSIR Publications
- →
- CSIR ScienceScope
- →
- View Item
| dc.contributor.author |
Marais, Laurette
|
|
| dc.contributor.author |
Van Zijl, L
|
|
| dc.date.accessioned | 2021-04-30T09:30:34Z | |
| dc.date.available | 2021-04-30T09:30:34Z | |
| dc.date.issued | 2018-09 | |
| dc.identifier.citation | Marais, L. & Van Zijl, L. 2018. The state complexity of language operations on XNFA-succinct unary regular languages. http://hdl.handle.net/10204/12002 . | en_ZA |
| dc.identifier.isbn | 978-1-4503-6647-2 | |
| dc.identifier.uri | https://doi.org/10.1145/3278681.3278684 | |
| dc.identifier.uri | https://dl.acm.org/doi/10.1145/3278681.3278684 | |
| dc.identifier.uri | http://hdl.handle.net/10204/12002 | |
| dc.description.abstract | Given two unary languages accepted by symmetric difference non-deterministic finite automata, we establish bounds on the state complexity of their union, intersection, relative complement and symmetric difference. For languages L1 and L2 accepted by minimal symmetric difference nondeterministic finite automata of size m and n respectively, we show that the state complexity of their union, intersection and relative complement has an upper bound of (2m - 1)(2n - 1). | en_US |
| dc.format | Abstract | en_US |
| dc.language.iso | en | en_US |
| dc.relation.uri | https://saicsit.mandela.ac.za/Programmes/Conference-Proper-Day-1 | en_US |
| dc.source | 2018 Annual Conference of the South African Institute of Computer Scientists and Information Technologists (SAICSIT), Port Elizabeth, South Africa, 26-28 September 2018 | en_US |
| dc.subject | XNFA-succinct | en_US |
| dc.subject | Unary regular languages | en_US |
| dc.subject | Descriptional complexity | en_US |
| dc.subject | Language operations | en_US |
| dc.subject | Nondeterminism | en_US |
| dc.title | The state complexity of language operations on XNFA-succinct unary regular languages | en_US |
| dc.type | Conference Presentation | en_US |
| dc.description.pages | 20-28 | en_US |
| dc.description.cluster | Meraka Institute | |
| dc.description.impactarea | Human Languages Technologies | en_US |
| dc.identifier.apacitation | Marais, L., & Van Zijl, L. (2018). The state complexity of language operations on XNFA-succinct unary regular languages. http://hdl.handle.net/10204/12002 | en_ZA |
| dc.identifier.chicagocitation | Marais, Laurette, and L Van Zijl. "The state complexity of language operations on XNFA-succinct unary regular languages." <i>2018 Annual Conference of the South African Institute of Computer Scientists and Information Technologists (SAICSIT), Port Elizabeth, South Africa, 26-28 September 2018</i> (2018): http://hdl.handle.net/10204/12002 | en_ZA |
| dc.identifier.vancouvercitation | Marais L, Van Zijl L, The state complexity of language operations on XNFA-succinct unary regular languages; 2018. http://hdl.handle.net/10204/12002 . | en_ZA |
| dc.identifier.ris | TY - Conference Presentation AU - Marais, Laurette AU - Van Zijl, L AB - Given two unary languages accepted by symmetric difference non-deterministic finite automata, we establish bounds on the state complexity of their union, intersection, relative complement and symmetric difference. For languages L1 and L2 accepted by minimal symmetric difference nondeterministic finite automata of size m and n respectively, we show that the state complexity of their union, intersection and relative complement has an upper bound of (2m - 1)(2n - 1). DA - 2018-09 DB - ResearchSpace DP - CSIR J1 - 2018 Annual Conference of the South African Institute of Computer Scientists and Information Technologists (SAICSIT), Port Elizabeth, South Africa, 26-28 September 2018 KW - XNFA-succinct KW - Unary regular languages KW - Descriptional complexity KW - Language operations KW - Nondeterminism LK - https://researchspace.csir.co.za PY - 2018 SM - 978-1-4503-6647-2 T1 - The state complexity of language operations on XNFA-succinct unary regular languages TI - The state complexity of language operations on XNFA-succinct unary regular languages UR - http://hdl.handle.net/10204/12002 ER - | en_ZA |
| dc.identifier.worklist | 21705 | en_US |
