The state complexity of language operations on XNFA-succinct unary regular languages
| Autor: | Laurette Marais, Lynette van Zijl |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Finite-state machine Unary operation 0102 computer and information sciences 02 engineering and technology 01 natural sciences Upper and lower bounds State complexity Intersection Regular language 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Nondeterministic finite automaton Symmetric difference Computer Science::Formal Languages and Automata Theory Mathematics |
| Zdroj: | SAICSIT |
| Popis: | 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). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|