Document Open Access Logo

A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton

Author Mikhail Raskin

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2018.138.pdf
  • Filesize: 439 kB
  • 11 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
Keywords
  • unambiguous automata
  • language complement
  • lower bound

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Unambiguous non-deterministic finite automata (UFA) are non-deterministic automata (over finite words) such that there is at most one accepting run over each input. Such automata are known to be potentially exponentially more succinct than deterministic automata, and non-deterministic automata can be exponentially more succinct than them.
In this paper we establish a superpolynomial lower bound for the state complexity of the translation of an UFA to a non-deterministic automaton for the complement language. This disproves the formerly conjectured polynomial upper bound for this translation. This lower bound only involves a one letter alphabet, and makes use of the random graph methods.
The same proof also shows that the translation of sweeping automata to non-deterministic automata is superpolynomial.

Cite As Get BibTex

Mikhail Raskin. A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 138:1-138:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.138

Author Details

Mikhail Raskin
  • LaBRI, University of Bordeaux, 351, cours de la Libération F-33405 Talence cedex, France

Funding

  • Raskin, Mikhail: This work was supported by the French National Research Agency (ANR project GraphEn / ANR-15-CE40-0009)

References

  1. Jean-Camille Birget. Partial orders on words, minimal elements of regular languages and state complexity. Theor. Comput. Sci., 119(2):267-291, 1993. URL: http://dx.doi.org/10.1016/0304-3975(93)90160-U.
  2. Marek Chrobak. Finite automata and unary languages. Theor. Comput. Sci., 47(3):149-158, 1986. URL: http://dx.doi.org/10.1016/0304-3975(86)90142-8.
  3. Thomas Colcombet. Unambiguity in automata theory. In Jeffrey Shallit and Alexander Okhotin, editors, Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings, volume 9118 of Lecture Notes in Computer Science, pages 3-18. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-19225-3_1.
  4. Viliam Geffert, Carlo Mereghetti, and Giovanni Pighizzini. Complementing two-way finite automata. Inf. Comput., 205(8):1173-1187, 2007. URL: http://dx.doi.org/10.1016/j.ic.2007.01.008.
  5. Tao Jiang, Edward McDowell, and Bala Ravikumar. The structure and complexity of minimal nfa’s over a unary alphabet. Int. J. Found. Comput. Sci., 2(2):163-182, 1991. URL: http://dx.doi.org/10.1142/S012905419100011X.
  6. Jozef Jirásek Jr., Galina Jirásková, and Juraj Sebej. Operations on unambiguous finite automata. In Srecko Brlek and Christophe Reutenauer, editors, Developments in Language Theory - 20th International Conference, DLT 2016, Montréal, Canada, July 25-28, 2016, Proceedings, volume 9840 of Lecture Notes in Computer Science, pages 243-255. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53132-7_20.
  7. Michal Kunc and Alexander Okhotin. State complexity of operations on two-way finite automata over a unary alphabet. Theor. Comput. Sci., 449:106-118, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.04.010.
  8. Hing Leung. Descriptional complexity of nfa of different ambiguity. Int. J. Found. Comput. Sci., 16(5):975-984, 2005. URL: http://dx.doi.org/10.1142/S0129054105003418.
  9. Hing Leung. Structurally unambiguous finite automata. In Oscar H. Ibarra and Hsu-Chun Yen, editors, Implementation and Application of Automata, 11th International Conference, CIAA 2006, Taipei, Taiwan, August 21-23, 2006, Proceedings, volume 4094 of Lecture Notes in Computer Science, pages 198-207. Springer, 2006. URL: http://dx.doi.org/10.1007/11812128_19.
  10. Oleg B Lupanov. A comparison of two types of finite automata. Problemy Kibernetiki, 9:321-326, 1963. Google Scholar
  11. J.I. Lyubich. Estimates of the number of states that arise in the determinization of a nondeterministic autonomous automaton. Sov. Math., Dokl., 5:345-348, 1964. Google Scholar
  12. Filippo Mera and Giovanni Pighizzini. Complementing unary nondeterministic automata. Theor. Comput. Sci., 330(2):349-360, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2004.04.015.
  13. Alexander Okhotin. Unambiguous finite automata over a unary alphabet. Inf. Comput., 212:15-36, 2012. URL: http://dx.doi.org/10.1016/j.ic.2012.01.003.
  14. Seppo Sippu and Eljas Soisalon-Soininen. Parsing Theory. Vol. 1: Languages and Parsing. Springer-Verlag New York, Inc., New York, NY, USA, 1988. Google Scholar
  15. Richard Edwin Stearns and Harry B. Hunt III. On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata. SIAM J. Comput., 14(3):598-611, 1985. URL: http://dx.doi.org/10.1137/0214044.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact