Search

Your search keyword '"Salomaa, Arto"' showing total 2,787 results
Start Over Author "Salomaa, Arto"

Refine your results

more »

more »

more »

more »
2,787 results on '"Salomaa, Arto"'

1. Descriptional Complexity of Finite Automata -- Selected Highlights

Author

Salomaa, Arto, Salomaa, Kai, and Smith, Taylor J.

Subjects
Computer Science - Formal Languages and Automata Theory
Abstract

The state complexity, respectively, nondeterministic state complexity of a regular language $L$ is the number of states of the minimal deterministic, respectively, of a minimal nondeterministic finite automaton for $L$. Some of the most studied state complexity questions deal with size comparisons of nondeterministic finite automata of differing degree of ambiguity. More generally, if for a regular language we compare the size of description by a finite automaton and by a more powerful language definition mechanism, such as a context-free grammar, we encounter non-recursive trade-offs. Operational state complexity studies the state complexity of the language resulting from a regularity preserving operation as a function of the complexity of the argument languages. Determining the state complexity of combined operations is generally challenging and for general combinations of operations that include intersection and marked concatenation it is uncomputable.

Published
2023

2. Parikh Matrices: Subword Indicators and Degrees of Ambiguity

Author

Salomaa, Arto, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Böckenhauer, Hans-Joachim, editor, Komm, Dennis, editor, and Unger, Walter, editor

Published
2018
Full Text
View/download PDF

4. Descriptional Complexity of Finite Automata – Selected Highlights.

Author

Salomaa, Arto, Salomaa, Kai, and Smith, Taylor J.

Subjects
*FINITE state machines, *LINGUISTIC complexity, *LANGUAGE policy, *KOLMOGOROV complexity, *ROBOTS, *GRAMMAR, *AMBIGUITY
Abstract

The state complexity, respectively, nondeterministic state complexity of a regular language L is the number of states of the minimal deterministic, respectively, of a minimal nondeterministic finite automaton for L. Some of the most studied state complexity questions deal with size comparisons of nondeterministic finite automata of differing degree of ambiguity. More generally, if for a regular language we compare the size of description by a finite automaton and by a more powerful language definition mechanism, such as a context-free grammar, we encounter non-recursive trade-offs. Operational state complexity studies the state complexity of the language resulting from a regularity preserving operation as a function of the complexity of the argument languages. Determining the state complexity of combined operations is generally challenging and for general combinations of operations that include intersection and marked concatenation it is uncomputable. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

8. Minimal Reaction Systems Defining Subset Functions

Author

Salomaa, Arto, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Calude, Cristian S., editor, Freivalds, Rūsiņš, editor, and Kazuo, Iwama, editor

Published
2014
Full Text
View/download PDF

12. Nondeterministic Trajectories

Author

Mateescu, Alexandru, Salomaa, Arto, Goos, G., editor, Hartmanis, J., editor, van Leeuwen, J., editor, Brauer, Wilfried, editor, Ehrig, Hartmut, editor, Karhumäki, Juhani, editor, and Salomaa, Arto, editor

Published
2002
Full Text
View/download PDF

13. Undecidability of State Complexities Using Mirror Images

Author

Salomaa, Arto, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Bordihn, Henning, editor, Kutrib, Martin, editor, and Truthe, Bianca, editor

Published
2012
Full Text
View/download PDF

14. On State Sequences Defined by Reaction Systems

Author

Salomaa, Arto, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Constable, Robert L., editor, and Silva, Alexandra, editor

Published
2012
Full Text
View/download PDF

15. Composition Sequences and Synchronizing Automata

Author

Salomaa, Arto, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Dinneen, Michael J., editor, Khoussainov, Bakhadyr, editor, and Nies, André, editor

Published
2012
Full Text
View/download PDF

16. Undecidability of the State Complexity of Composed Regular Operations

Author

Salomaa, Arto, Salomaa, Kai, Yu, Sheng, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Dediu, Adrian-Horia, editor, Inenaga, Shunsuke, editor, and Martín-Vide, Carlos, editor

Published
2011
Full Text
View/download PDF

17. On Some Biologically Motivated Control Devices for Parallel Rewriting

Author

Salomaa, Arto, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Kelemen, Jozef, editor, and Kelemenová, Alica, editor

Published
2011
Full Text
View/download PDF

19. Splicing Revisited

Author

Păun, Gheorghe, Rozenberg, Grzegorz, Salomaa, Arto, Brauer, Wilfried, editor, Rozenberg, Grzegorz, editor, Salomaa, Arto, editor, and Păun, Gheorghe

Published
1998
Full Text
View/download PDF

21. Splicing Systems

Author

Păun, Gheorghe, Rozenberg, Grzegorz, Salomaa, Arto, Brauer, Wilfried, editor, Rozenberg, Grzegorz, editor, Salomaa, Arto, editor, and Păun, Gheorghe

Published
1998
Full Text
View/download PDF

22. Splicing Circular Strings

Author

Păun, Gheorghe, Rozenberg, Grzegorz, Salomaa, Arto, Brauer, Wilfried, editor, Rozenberg, Grzegorz, editor, Salomaa, Arto, editor, and Păun, Gheorghe

Published
1998
Full Text
View/download PDF

23. Watson—Crick Automata

Author

Păun, Gheorghe, Rozenberg, Grzegorz, Salomaa, Arto, Brauer, Wilfried, editor, Rozenberg, Grzegorz, editor, Salomaa, Arto, editor, and Păun, Gheorghe

Published
1998
Full Text
View/download PDF

24. Insertion-Deletion Systems

Author

Păun, Gheorghe, Rozenberg, Grzegorz, Salomaa, Arto, Brauer, Wilfried, editor, Rozenberg, Grzegorz, editor, Salomaa, Arto, editor, and Păun, Gheorghe

Published
1998
Full Text
View/download PDF

27. Distributed H Systems

Author

Păun, Gheorghe, Rozenberg, Grzegorz, Salomaa, Arto, Brauer, Wilfried, editor, Rozenberg, Grzegorz, editor, Salomaa, Arto, editor, and Păun, Gheorghe

Published
1998
Full Text
View/download PDF

30. Length Codes, Products of Languages and Primality

Author

Salomaa, Arto, Salomaa, Kai, Yu, Sheng, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Martín-Vide, Carlos, editor, Otto, Friedrich, editor, and Fernau, Henning, editor

Published
2008
Full Text
View/download PDF

32. Shuffle-like operations on ω-words

Author

Mateescu, Alexandru, Mateescu, George Daniel, Rozenberg, Grzegorz, Salomaa, Arto, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Păun, Gheorghe, editor, and Salomaa, Arto, editor

Published
1997
Full Text
View/download PDF

35. L Systems

Author

Kari, Lila, Rozenberg, Grzegorz, Salomaa, Arto, Rozenberg, Grzegorz, editor, and Salomaa, Arto, editor

Published
1997
Full Text
View/download PDF

40. Knapsack Systems

Author

Salomaa, Arto, Brauer, Wilfried, editor, Rozenberg, Grzegorz, editor, and Salomaa, Arto, editor

Published
1996
Full Text
View/download PDF

41. RSA

Author

Salomaa, Arto, Brauer, Wilfried, editor, Rozenberg, Grzegorz, editor, and Salomaa, Arto, editor

Published
1996
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results