research-article

Limitations of lower bound methods for deterministic nested word automata

Author:

Kai SalomaaAuthors Info & Claims

Information and Computation, Volume 209, Issue 3

Pages 580 - 589

https://doi.org/10.1016/j.ic.2010.11.021

Published: 01 March 2011 Publication History

Abstract

Finite automata operating on nested words were introduced by Alur and Madhusudan in 2006. While nested word automata retain many of the desirable properties of ordinary finite automata, there is no known efficient minimization algorithm for deterministic nested word automata and, interestingly, state complexity bounds for nested word automata turn out to differ significantly from the corresponding bounds for ordinary finite automata. Consequently lower bounds for the state complexity of nested word languages need to rely on fooling set type techniques. We discuss limitations of the techniques and show that, even in the deterministic case, the bounds given by the lower bound methods may be arbitrarily far away from the actual state complexity of the nested word language.

References

[1]

Congruences for visibly pushdown languages. In: Lect. Notes Comput. Sci., vol. 3580. Springer. pp. 1102-1114.

Digital Library

[2]

Alur, R. and Madhusudan, P., Adding nesting structure to words. In: Ibarra, O.H., Dang, Z. (Eds.), Lect. Notes Comput. Sci., vol. 4036. Springer. pp. 1-13.

Digital Library

[3]

Alur, R. and Madhusudan, P., Adding nesting structure to words. J. Assoc. Comput. Mach. v56 i3.

Digital Library

[4]

Arenas, M., Barceló, P. and Libkin, L., Regular languages of nested words: Fixed points, automata and synchronization. In: Lect. Notes Comput. Sci., vol. 4596. Springer. pp. 888-900.

Digital Library

[5]

Birget, J.-C., Intersection and union of regular languages and state complexity. Inform. Process. Lett. v43. 185-190.

Digital Library

[6]

Chervet, P. and Walukiewicz, I., Minimizing variants of visibly pushdown automata. In: Lect. Notes Comput. Sci., vol. 4708. Springer. pp. 135-146.

Digital Library

[7]

Champavère, J., Gilleron, R., Lemay, A. and Niehren, J., Efficient inclusion checking for deterministic tree automata and XML schemas. Inform. Comput. 1181-1208.

Digital Library

[8]

H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, C. Löding, S. Tison, M. Tommasi, Tree Automata Techniques and Applications, 2007, Electronic book available from: <tata.gforge.inria.fr>.

[9]

Domaratzki, M. and Salomaa, K., Lower bounds for the transition complexity of NFAs. J. Comput. System Sci. v74. 1116-1130.

Digital Library

[10]

Gauwin, O., Niehren, J. and Roos, Y., Streaming tree automata. Inform. Process. Lett. v109. 13-17.

Digital Library

[11]

F. Gécseg, M. Steinby, Tree languages, in: {30}, vol. III, pp. 1--68.

Digital Library

[12]

Gruber, H. and Holzer, M., Finding lower bounds for the nondeterministic state complexity is hard. In: Ibarra, O.H., Dang, Z. (Eds.), Lect. Notes Comput. Sci., vol. 4036. Springer. pp. 363-374.

Digital Library

[13]

H. Gruber, M. Holzer, Finding lower bounds for the nondeterministic state complexity is hard, Electronic Colloquium on Computational Complexity, Report No. 27, 2006 (full version of {12}).

[14]

Gruber, H. and Holzer, M., Inapproximability of nondeterministic state and transition complexity assuming P≠NP. In: Harju, T., Karhumäki, J., Lepistö, A. (Eds.), Lect. Notes Comput. Sci., vol. 4588. Springer-Verlag. pp. 205-216.

Digital Library

[15]

Han, Y.-S. and Salomaa, K., Nondeterministic state complexity of nested word automata. Theoret. Comput. Sci. v410. 2961-2971.

Digital Library

[16]

Holzer, M. and Kutrib, M., Nondeterministic descriptional complexity of regular languages. Internat. J. Found. Comput. Sci. v14. 1087-1102.

[17]

Holzer, M. and Kutrib, M., Nondeterministic finite automata -- recent results on the descriptional and computational complexity. In: Ibarra, O.H., Revikumar, B. (Eds.), Lect. Notes Comput. Sci., vol. 5148. Springer. pp. 1-16.

Digital Library

[18]

Holzer, M. and Kutrib, M., Descriptional and computational complexity of finite automata. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (Eds.), Lect. Notes Comput. Sci., vol. 5457. Springer. pp. 23-42.

Digital Library

[19]

Hromkovič, J., Communication Complexity and Parallel Computing. 1997. Springer-Verlag.

Digital Library

[20]

Hromkovič, J., Petersen, H. and Schnitger, G., On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFAs. Theoret. Comput. Sci. v410. 2972-2981.

Digital Library

[21]

Jirásková, G., Note on minimal automata and uniform communication protocols. In: Martín-Vide, C., Mitrana, V. (Eds.), Topics in Computer Mathematics, vol. 9. Taylor & Francis. pp. 163-170.

[22]

Jirásková, G., State complexity of some operations on binary regular languages. Theoret. Comput. Sci. v330. 287-298.

Digital Library

[23]

Kameda, T. and Weiner, P., On the state minimization of nondeterministic finite automata. IEEE Trans. Computers. vC-19 i7. 617-627.

Digital Library

[24]

Kumar, V., Madhusudan, P. and Viswanathan, M., Minimization, learning, and conformance testing of Boolean programs. In: Lect. Notes Comput. Sci., vol. 4137. Springer. pp. 203-217.

Digital Library

[25]

Liu, G., Martin-Vide, C., Salomaa, A. and Yu, S., The state-complexity of two combined operations: Star of catenation and star of reversal. Inform. Comput. v206. 1178-1186.

Digital Library

[26]

Piao, X. and Salomaa, K., Operational state complexity of nested word automata. Theoret. Comput. Sci. v410. 3290-3302.

Digital Library

[27]

X. Piao, K. Salomaa, Transformations between different types of bottom-up unranked tree automata, in: I. McQuillan, G. Pighizzini, B. Trost (Eds.), Proc. 12th International Workshop Descriptional Complexity of Formal Systems, DCFS 2010, Saskatoon, Canada, 2010, pp. 193--204.

[28]

Neumann, A. and Seidl, H., Locating matches of tree patterns in forests. In: Lect. Notes Comput. Sci., vol. 1530. Springer. pp. 134-146.

Digital Library

[29]

H. Nguyen, VPAlib: Visibly pushdown automata library, 2006. Available from: <http://www.emn.fr/x-info/hnguyen/vpa>.

[30]

. In: Rozenberg, G., Salomaa, A. (Eds.), Handbook of Formal Languages, vols. I--III. Springer-Verlag.

Digital Library

[31]

Salomaa, K., State complexity of nested word automata. In: Dediu, A.H., Ionescu, A.M., Martin-Vide, C. (Eds.), Lect. Notes Comput. Sci., vol. 5457. Springer. pp. 59-70.

Digital Library

[32]

Shallit, J., A Second Course in Formal Languages and Automata Theory. 2009. Cambridge University Press.

Digital Library

[33]

S. Yu, Grail+: A symbolic computation environment for finite-state machines, regular expressions and finite languages, 2002, Available from: <http://www.csd.uwo.ca/Research/grail>.

[34]

S. Yu, Regular languages, in: {30}, vol. I, pp. 41--110.

Digital Library

Cited By

Okhotin ASalomaa K(2019)Descriptional complexity of unambiguous input-driven pushdown automataTheoretical Computer Science10.1016/j.tcs.2014.11.015566:C(1-11)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.tcs.2014.11.015
Okhotin ASalomaa K(2018)Further Closure Properties of Input-Driven Pushdown AutomataDescriptional Complexity of Formal Systems10.1007/978-3-319-94631-3_19(224-236)Online publication date: 25-Jul-2018
https://dl.acm.org/doi/10.1007/978-3-319-94631-3_19
Okhotin ASalomaa K(2017)State complexity of operations on input-driven pushdown automataJournal of Computer and System Sciences10.1016/j.jcss.2017.02.00186:C(207-228)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1016/j.jcss.2017.02.001
Show More Cited By

Limitations of lower bound methods for deterministic nested word automata
1. Theory of computation

Recommendations

Operational state complexity of nested word automata

We introduce techniques to prove lower bounds for the number of states needed by finite automata operating on nested words. We study the state complexity of Boolean operations and obtain lower bounds that are tight within an additive constant. The ...
Descriptional complexity of determinization and complementation for finite automata
CATS 2011: Proceedings of the Seventeenth Computing on The Australasian Theory Symposium - Volume 119

In this paper we study the subset construction that transforms nondeterministic finite automata (NFA) to deterministic finite automata (DFA). It is well known that given a n-state NFA, the subset construction algorithm produces a 2ⁿ-state DFA in the ...
Descriptional complexity of determinization and complementation for finite automata
CATS '11: Proceedings of the Seventeenth Computing: The Australasian Theory Symposium - Volume 119

In this paper we study the subset construction that transforms nondeterministic finite automata (NFA) to deterministic finite automata (DFA). It is well known that given a n-state NFA, the subset construction algorithm produces a 2ⁿ-state DFA in the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Computation

Information and Computation Volume 209, Issue 3

March, 2011

378 pages

ISSN:0890-5401

Issue’s Table of Contents

Copyright © Elsevier Inc.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 March 2011

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Okhotin ASalomaa K(2019)Descriptional complexity of unambiguous input-driven pushdown automataTheoretical Computer Science10.1016/j.tcs.2014.11.015566:C(1-11)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.tcs.2014.11.015
Okhotin ASalomaa K(2018)Further Closure Properties of Input-Driven Pushdown AutomataDescriptional Complexity of Formal Systems10.1007/978-3-319-94631-3_19(224-236)Online publication date: 25-Jul-2018
https://dl.acm.org/doi/10.1007/978-3-319-94631-3_19
Okhotin ASalomaa K(2017)State complexity of operations on input-driven pushdown automataJournal of Computer and System Sciences10.1016/j.jcss.2017.02.00186:C(207-228)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1016/j.jcss.2017.02.001
Okhotin ASalomaa K(2014)Complexity of input-driven pushdown automataACM SIGACT News10.1145/2636805.263682145:2(47-67)Online publication date: 9-Jun-2014
https://dl.acm.org/doi/10.1145/2636805.2636821
Okhotin ASalomaa K(2011)State complexity of operations on input-driven pushdown automataProceedings of the 36th international conference on Mathematical foundations of computer science10.5555/2034006.2034052(485-496)Online publication date: 22-Aug-2011
https://dl.acm.org/doi/10.5555/2034006.2034052
Okhotin ASalomaa K(2011)Descriptional complexity of unambiguous nested word automataProceedings of the 5th international conference on Language and automata theory and applications10.5555/2022896.2022931(414-426)Online publication date: 26-May-2011
https://dl.acm.org/doi/10.5555/2022896.2022931

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents