Document Open Access Logo

On the Complexity of Universality for Partially Ordered NFAs

Authors Markus Krötzsch, Tomás Masopust, Michaël Thomazo

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.61.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Markus Krötzsch
Tomás Masopust
Michaël Thomazo

Cite AsGet BibTex

Markus Krötzsch, Tomás Masopust, and Michaël Thomazo. On the Complexity of Universality for Partially Ordered NFAs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.61

Abstract

Partially ordered nondeterminsitic finite automata (poNFAs) are NFAs whose transition relation induces a partial order on states, i.e., for which cycles occur only in the form of self-loops on a single state. A poNFA is universal if it accepts all words over its input alphabet. Deciding universality is \PSpace-complete for poNFAs, and we show that this remains true even when restricting to a fixed alphabet. This is nontrivial since standard encodings of alphabet symbols in, e.g., binary can turn self-loops into longer cycles. A lower coNP-complete complexity bound can be obtained if we require that all self-loops in the poNFA are deterministic, in the sense that the symbol read in the loop cannot occur in any other transition from that state. We find that such restricted poNFAs (rpoNFAs) characterise the class of R-trivial languages, and we establish the complexity of deciding if the language of an NFA is R-trivial. Nevertheless, the limitation to fixed alphabets turns out to be essential even in the restricted case: deciding universality of rpoNFAs with unbounded alphabets is PSPACE-complete. Our results also prove the complexity of the inclusion and equivalence problems, since universality provides the lower bound, while the upper bound is mostly known or proved in the paper.
Keywords
  • automata
  • nondeterminism
  • partial order
  • universality

Metrics

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

References

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. Google Scholar
  2. Jorge Almeida, Jana Bartoňová, Ondřej Klíma, and Michal Kunc. On decidability of intermediate levels of concatenation hierarchies. In Developments in Language Theory, volume 9168 of LNCS, pages 58-70. Springer, 2015. Google Scholar
  3. Yehoshua Bar-Hillel, Micha A. Perles, and Eli Shamir. On formal properties of simple phrase structure grammars. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14:143-172, 1961. Google Scholar
  4. Pablo Barceló, Leonid Libkin, and Juan L. Reutter. Querying regular graph patterns. Journal of the ACM, 61(1):8:1-8:54, 2014. Google Scholar
  5. Geert Jan Bex, Wouter Gelade, Wim Martens, and Frank Neven. Simplifying XML schema: Effortless handling of nondeterministic regular expressions. In ACM SIGMOD International Conference on Management of Data, pages 731-744. ACM, 2009. Google Scholar
  6. Ahmed Bouajjani, Anca Muscholl, and Tayssir Touilim. Permutation rewriting and algorithmic verification. Information and Computation, 205(2):199-224, 2007. Google Scholar
  7. Anne Brüggemann-Klein and Derick Wood. One-unambiguous regular languages. Information and Computation, 142(2):182-206, 1998. Google Scholar
  8. Janus A. Brzozowski and Robert Knast. The dot-depth hierarchy of star-free languages is infinite. Journal of Computer and System Sciences, 16(1):37-55, 1978. Google Scholar
  9. Janusz A. Brzozowski and Faith E. Fich. Languages of R-trivial monoids. Journal of Computer and System Sciences, 20(1):32-49, 1980. Google Scholar
  10. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. Reasoning on regular path queries. SIGMOD Record, 32(4):83-92, 2003. Google Scholar
  11. Rina S. Cohen and Janusz A. Brzozowski. Dot-depth of star-free events. Journal of Computer and System Sciences, 5(1):1-16, 1971. Google Scholar
  12. Wojciech Czerwinski, Claire David, Katja Losemann, and Wim Martens. Deciding definability by deterministic regular expressions. In International Conference on Foundations of Software Science and Computation Structures, volume 7794 of LNCS, pages 289-304. Springer, 2013. Google Scholar
  13. Keith Ellul, Bryan Krawetz, Jeffrey Shallit, and Ming-Wei Wang. Regular expressions: New results and open problems. Journal of Automata, Languages and Combinatorics, 10(4):407-437, 2005. Google Scholar
  14. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  15. Christian Glaßer and Heinz Schmitz. Languages of dot-depth 3/2. Theory of Computing Systems, 42(2):256-286, 2008. Google Scholar
  16. Piotr Hofman and Wim Martens. Separability by short subsequences and subwords. In International Conference on Database Theory, volume 31 of LIPIcs, pages 230-246, 2015. Google Scholar
  17. Harry B. Hunt III and Daniel J. Rosenkrantz. Computational parallels between the regular and context-free languages. SIAM Journal on Computing, 7(1):99-114, 1978. Google Scholar
  18. Ondřej Klíma and Libor Polák. Alternative automata characterization of piecewise testable languages. In Developments in Language Theory, volume 7907 of LNCS, pages 289-300. Springer, 2013. Google Scholar
  19. Markus Krötzsch, Tomáš Masopust, and Michaël Thomazo. On the complexity of universality for partially ordered NFAs. Technical report. URL: https://ddll.inf.tu-dresden.de/web/Inproceedings3086.
  20. Manfred Kufleitner and Alexander Lauser. Partially ordered two-way Büchi automata. International Journal of Foundations of Computer Science, 22(8):1861-1876, 2011. Google Scholar
  21. Kamal Lodaya, Paritosh K. Pandya, and Simoni S. Shah. Around dot depth two. In Developments in Language Theory, volume 6224 of LNCS, pages 303-315. Springer, 2010. Google Scholar
  22. Wim Martens, Frank Neven, and Thomas Schwentick. Complexity of decision problems for XML schemas and chain regular expressions. SIAM Journal on Computing, 39(4):1486-1530, 2009. Google Scholar
  23. Tomáš Masopust. Piecewise testable languages and nondeterministic automata. In Mathematical Foundations of Computer Science, volume 58 of LIPIcs, pages 68:1-68:14, 2016. Google Scholar
  24. Tomáš Masopust and Michaël Thomazo. On the complexity of k-piecewise testability and the depth of automata. In Developments in Language Theory, volume 9168 of LNCS, pages 364-376. Springer, 2015. Google Scholar
  25. Alfred R. Meyer and Larry J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In Symposium on Switching and Automata Theory (SWAT/FOCS), pages 125-129. IEEE Computer Society, 1972. Google Scholar
  26. Jean-Éric Pin. Varieties Of Formal Languages. Plenum Press, New York, 1986. Google Scholar
  27. Thomas Place and Marc Zeitoun. Separation and the successor relation. In Symposium on Theoretical Aspects of Computer Science, volume 30 of LIPIcs, pages 662-675, 2015. Google Scholar
  28. Narad Rampersad, Jeffrey Shallit, and Zhi Xu. The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages. Fundamenta Informatica, 116(1-4):223-236, 2012. Google Scholar
  29. Heinz Schmitz. The forbidden pattern approach to concatenation hierachies. PhD thesis, University of Würzburg, 2000. Google Scholar
  30. Marcel P. Schützenberger. Sur le produit de concatenation non ambigu. Semigroup Forum, 13(1):47-75, 1976. Google Scholar
  31. Thomas Schwentick, Denis Thérien, and Heribert Vollmer. Partially-ordered two-way automata: A new characterization of DA. In Developments in Language Theory, volume 2295 of LNCS, pages 239-250. Springer, 2001. Google Scholar
  32. Imre Simon. Hierarchies of Events with Dot-Depth One. PhD thesis, Department of Applied Analysis and Computer Science, University of Waterloo, Canada, 1972. Google Scholar
  33. Giorgio Stefanoni, Boris Motik, Markus Krötzsch, and Sebastian Rudolph. The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases. Journal of Artificial Intelligence Research, 51:645-705, 2014. Google Scholar
  34. Larry J. Stockmeyer and Albert R. Meyer. Word problems requiring exponential time: Preliminary report. In ACM Symposium on the Theory of Computing, pages 1-9. ACM, 1973. Google Scholar
  35. Howard Straubing. A generalization of the Schützenberger product of finite monoids. Theoretical Computer Science, 13:137-150, 1981. Google Scholar
  36. Howard Straubing. Finite semigroup varieties of the form V*D. Journal of Pure and Applied Algebra, 36:53-94, 1985. Google Scholar
  37. Denis Thérien. Classification of finite monoids: The language approach. Theoretical Computer Science, 14:195-208, 1981. Google Scholar
  38. Klaus W. Wagner. Leaf language classes. In Machines, Computations, and Universality, volume 3354 of LNCS, pages 60-81. Springer, 2004. Google Scholar
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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact