article

State complexity of basic language operations combined with reversal

Authors:

Carlos Martin-Vide,

Sheng YuAuthors Info & Claims

Information and Computation, Volume 206, Issue 9-10

Pages 1178 - 1186

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

Published: 01 September 2008 Publication History

Abstract

We study the state complexity of combined operations on regular languages. Each of the combined operations is a basic operation combined with reversal. We show that their state complexities are all very different from the compositions of state complexities of individual operations.

References

[1]

Jeffrey E.F. Friedl, Mastering Regular Expressions, O'Reilly, 1997.

Digital Library

[2]

Yuan Gao, Kai Salomaa, Sheng Yu, State complexity of star of catenation and reversal, in: Descriptional Complexity of Formal Systems (DCFS 2006), pp. 153--164.

[3]

Gill, Arthur and Kou, Lawrence T., Multiple-entry finite automata. Journal of Computer and System Sciences. v9 i1. 1-19.

Digital Library

[4]

Harel, David and Politi, Michal, Modeling Reactive Systems with Statecharts. 1998. McGraw-Hill.

Digital Library

[5]

Hopcroft, John E. and Ullman, Jeffrey D., Introduction to Automata Theory, Languages, and Computation. 1979. Addison Wesley, Reading, MA.

Digital Library

[6]

Gelina Jirásková, Alexander Okhotin, On the state complexity of star of union and star of intersection, Turku Center for Computer Science TUCS Technical Report No. 825, 2007.

[7]

Lauri Karttunen, Application of finite-state transducers in natural language processing, in: Proceedings of the 5th International Conference on Implementation and Application of Automata, LNCS, vol. 2088, 2001, pp. 34--46.

Digital Library

[8]

Linz, Peter, An Introduction to Formal Languages and Automata. 2006. fourth ed. Jones and Bartlett Publishers, Boston.

Digital Library

[9]

Salomaa, Arto, Theory of Automata. 1969. Pergamon Press, Oxford.

Digital Library

[10]

Salomaa, Arto, Salomaa, Kai and Yu, Sheng, State complexity of combined operations. Theoretical Computer Science. v383 i2--3. 140-152.

Digital Library

[11]

Salomaa, Arto, Wood, Derick and Yu, Sheng, On the state complexity of reversal of regular languages. Theoretical Computer Science. v320 i2--3. 315-329.

Digital Library

[12]

Salomaa, Kai and Yu, Sheng, On the state complexity of combined operations and their estimation. International Journal of Foundations of Computer Science. v18 i4. 683-698.

[13]

Yu, Sheng, Regular languages. In: Rozenberg, G., Salomaa, A. (Eds.), Handbook of Formal languages, vol. 1. Springer-Verlag. pp. 41-110.

Digital Library

[14]

Yu, Sheng, State complexity: recent results and open problems. Fundamenta Informaticae. v64 i1--4. 471-480.

Digital Library

[15]

Yu, Sheng, State complexity of regular languages. Journal of Automata, Languages and Combinatorics. v6 i2. 221-234.

Digital Library

[16]

Ilie Lucian, Sheng Yu, Qing Zhao, Introduction to process traces, in: Proceedings of the 2003 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'03), 2003, pp. 1706--1712.

[17]

Yu, Sheng, Zhuang, Qingyu and Salomaa, Kai, The state complexities of some basic operations on regular languages. Theoretical Computer Science. v125 i2. 315-328.

Digital Library

[18]

Grail+. Available from: <http://www.csd.uwo.ca/Research/grail/index.html>.

Cited By

Caron PLuque JPatrou B(2023)Operational State Complexity Revisited: The Contribution of Monsters and ModifiersDescriptional Complexity of Formal Systems10.1007/978-3-031-34326-1_1(1-20)Online publication date: 4-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-34326-1_1
Caron PDurand APatrou B(2023)The Exact State Complexity for the Composition of Root and ReversalDevelopments in Language Theory10.1007/978-3-031-33264-7_7(74-85)Online publication date: 12-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-33264-7_7
Piao XSalomaa K(2019)Transformations Between Different Models of Unranked Bottom-Up Tree AutomataFundamenta Informaticae10.5555/2361347.2361349109:4(405-424)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.5555/2361347.2361349
Show More Cited By

Index Terms

State complexity of basic language operations combined with reversal

Recommendations

State complexity of combined operations with two basic operations

This paper studies the state complexity of (L"1L"2)^R, L"1^RL"2, L"1^*L"2, (L"1@?L"2)L"3, (L"1@?L"2)L"3, L"1L"2@?L"3, and L"1L"2@?L"3 for regular languages L"1, L"2, and L"3. We first show that the upper bound proposed by Liu et al. (2008) [18] for the ...
State complexity of union and intersection of square and reversal on k regular languages

In this paper, we continue our study on the state complexity of combined operations on regular languages. We study the state complexities of @?"i"="1^kL"i^2, @?"i"="1^kL"i^2, @?"i"="1^kL"i^R, and @?"i"="1^kL"i^R, for regular languages L"i, 1@?i@?k, k>=...
State complexity of power

The number of states in a deterministic finite automaton (DFA) recognizing the language L^k, where L is regular language recognized by an n-state DFA, and k>=2 is a constant, is shown to be at most n2^(^k^-^1^)^n and at least (n-k)2^(^k^-^1^)^(^n^-^k^) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Computation

Information and Computation Volume 206, Issue 9-10

September, 2008

244 pages

ISSN:0890-5401

Issue’s Table of Contents

Copyright © © 2008.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 September 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Caron PLuque JPatrou B(2023)Operational State Complexity Revisited: The Contribution of Monsters and ModifiersDescriptional Complexity of Formal Systems10.1007/978-3-031-34326-1_1(1-20)Online publication date: 4-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-34326-1_1
Caron PDurand APatrou B(2023)The Exact State Complexity for the Composition of Root and ReversalDevelopments in Language Theory10.1007/978-3-031-33264-7_7(74-85)Online publication date: 12-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-33264-7_7
Piao XSalomaa K(2019)Transformations Between Different Models of Unranked Bottom-Up Tree AutomataFundamenta Informaticae10.5555/2361347.2361349109:4(405-424)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.5555/2361347.2361349
Jirásková GOkhotin A(2019)On the State Complexity of Star of Union and Star of IntersectionFundamenta Informaticae10.5555/2361328.2361331109:2(161-178)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.5555/2361328.2361331
Piao XSalomaa K(2019)State complexity of the concatenation of regular tree languagesTheoretical Computer Science10.1016/j.tcs.2011.12.048429(273-281)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.tcs.2011.12.048
Gao YKari L(2013)State complexity of star of union and square of union on k regular languagesTheoretical Computer Science10.1016/j.tcs.2013.06.003499(38-50)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1016/j.tcs.2013.06.003
Brzozowski JLiu D(2013)Universal witnesses for state complexity of basic operations combined with reversalProceedings of the 18th international conference on Implementation and Application of Automata10.1007/978-3-642-39274-0_8(72-83)Online publication date: 16-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39274-0_8
Gao YYu S(2012)State Complexity of Combined Operations with Union, Intersection, Star and ReversalFundamenta Informaticae10.5555/2385073.2385081116:1-4(79-92)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.5555/2385073.2385081
Gao YYu S(2011)State complexity of four combined operations composed of union, intersection, star and reversalProceedings of the 13th international conference on Descriptional complexity of formal systems10.5555/2032539.2032554(158-171)Online publication date: 25-Jul-2011
https://dl.acm.org/doi/10.5555/2032539.2032554
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
Show More Cited By

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