GLORIA

GEOMAR Library Ocean Research Information Access

X

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • World Scientific Pub Co Pte Ltd  (6)
Material
Publisher
  • World Scientific Pub Co Pte Ltd  (6)
Person/Organisation
Language
Years
  • 1
    Online Resource
    Online Resource
    State Complexity of Regular Tree Languages for Tree Matching
    World Scientific Pub Co Pte Ltd ; 2016
    In:  International Journal of Foundations of Computer Science Vol. 27, No. 08 ( 2016-12), p. 965-979
    Details
    In: International Journal of Foundations of Computer Science, World Scientific Pub Co Pte Ltd, Vol. 27, No. 08 ( 2016-12), p. 965-979
    Abstract: We study the state complexity of regular tree languages for tree matching problem. Given a tree t and a set of pattern trees L, we can decide whether or not there exists a subtree occurrence of trees in L from the tree t by considering the new language L′ which accepts all trees containing trees in L as subtrees. We consider the case when we are given a set of pattern trees as a regular tree language and investigate the state complexity. Based on the sequential and parallel tree concatenation, we define three types of tree languages for deciding the existence of different types of subtree occurrences. We also study the deterministic top-down state complexity of path-closed languages for the same problem.
    Type of Medium: Online Resource
    ISSN: 0129-0541 , 1793-6373
    URL: Article
    DOI: 10.1142/S0129054116500398
    Language: English
    Publisher: World Scientific Pub Co Pte Ltd
    Publication Date: 2016
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 2
    Online Resource
    Online Resource
    Generalizations of Code Languages with Marginal Errors
    World Scientific Pub Co Pte Ltd ; 2021
    In:  International Journal of Foundations of Computer Science Vol. 32, No. 05 ( 2021-08), p. 509-529
    Details
    In: International Journal of Foundations of Computer Science, World Scientific Pub Co Pte Ltd, Vol. 32, No. 05 ( 2021-08), p. 509-529
    Abstract: The [Formula: see text]-prefix-free, [Formula: see text] -suffix-free and [Formula: see text]-infix-free languages generalize the prefix-free, suffix-free and infix-free languages by allowing marginal errors. For example, a string [Formula: see text] in a [Formula: see text]-prefix-free language [Formula: see text] can be a prefix of up to [Formula: see text] different strings in [Formula: see text] . We also define finitely prefix-free languages in which a string [Formula: see text] can be a prefix of finitely many strings. We present efficient algorithms that determine whether or not a given regular language is [Formula: see text] -prefix-free, [Formula: see text]-suffix-free or [Formula: see text] -infix-free, and analyze the time complexity of the algorithms. We establish undecidability results for deciding these properties for (linear) context-free languages.
    Type of Medium: Online Resource
    ISSN: 0129-0541 , 1793-6373
    URL: Article
    DOI: 10.1142/S0129054121410057
    Language: English
    Publisher: World Scientific Pub Co Pte Ltd
    Publication Date: 2021
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 3
    Online Resource
    Online Resource
    Left is Better Than Right for Reducing Nondeterminism of NFAs
    World Scientific Pub Co Pte Ltd ; 2021
    In:  International Journal of Foundations of Computer Science Vol. 32, No. 05 ( 2021-08), p. 531-550
    Details
    In: International Journal of Foundations of Computer Science, World Scientific Pub Co Pte Ltd, Vol. 32, No. 05 ( 2021-08), p. 531-550
    Abstract: We study the NFA reductions by invariant equivalences and preorders. It is well-known that the NFA minimization problem is PSPACE-complete. Therefore, there have been many approaches to reduce the size of NFAs in low polynomial time by computing invariant equivalence or preorder relation and merging the states within same equivalence class. Here we consider the nondeterminism reduction of NFAs by invariant equivalences and preorders. We, in particular, show that computing equivalence and preorder relation from the left is more useful than the right for reducing the degree of nondeterminism in NFAs. We also present experimental evidence for showing that NFA reduction from the left achieves the better reduction of nondeterminism than reduction from the right.
    Type of Medium: Online Resource
    ISSN: 0129-0541 , 1793-6373
    URL: Article
    DOI: 10.1142/S0129054121410069
    Language: English
    Publisher: World Scientific Pub Co Pte Ltd
    Publication Date: 2021
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 4
    Online Resource
    Online Resource
    State Complexity of Insertion
    World Scientific Pub Co Pte Ltd ; 2016
    In:  International Journal of Foundations of Computer Science Vol. 27, No. 07 ( 2016-11), p. 863-878
    Details
    In: International Journal of Foundations of Computer Science, World Scientific Pub Co Pte Ltd, Vol. 27, No. 07 ( 2016-11), p. 863-878
    Abstract: It is well known that the resulting language obtained by inserting a regular language to a regular language is regular. We study the nondeterministic and deterministic state complexity of the insertion operation. Given two incomplete DFAs of sizes m and n, we give an upper bound ( m + 2 ) · 2 m n − m − 1 · 3 m and find a lower bound for an asymp-totically tight bound. We also present the tight nondeterministic state complexity by a fooling set technique. The deterministic state complexity of insertion is 2 Θ ( m n ) and the nondeterministic state complexity of insertion is precisely m n + 2 m , where m and n are the size of input finite automata. We also consider the state complexity of insertion in the case where the inserted language is bifix-free or non-returning.
    Type of Medium: Online Resource
    ISSN: 0129-0541 , 1793-6373
    URL: Article
    DOI: 10.1142/S0129054116500349
    Language: English
    Publisher: World Scientific Pub Co Pte Ltd
    Publication Date: 2016
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 5
    Online Resource
    Online Resource
    Operational State Complexity of Subtree-Free Regular Tree Languages
    World Scientific Pub Co Pte Ltd ; 2016
    In:  International Journal of Foundations of Computer Science Vol. 27, No. 06 ( 2016-09), p. 705-724
    Details
    In: International Journal of Foundations of Computer Science, World Scientific Pub Co Pte Ltd, Vol. 27, No. 06 ( 2016-09), p. 705-724
    Abstract: We introduce subtree-free regular tree languages that are closely related to XML schemas and investigate the state complexity of basic operations on subtree-free regular tree languages. The state complexity of an operation for regular tree languages is the number of states that are sufficient and necessary in the worst-case for the minimal deterministic ranked tree automaton that accepts the tree language obtained from the operation. We establish the precise state complexity of (sequential, parallel) concatenation, (bottom-up, top-down) star, intersection and union for subtree-free regular tree languages.
    Type of Medium: Online Resource
    ISSN: 0129-0541 , 1793-6373
    URL: Article
    DOI: 10.1142/S0129054116500246
    Language: English
    Publisher: World Scientific Pub Co Pte Ltd
    Publication Date: 2016
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 6
    Online Resource
    Online Resource
    THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE
    World Scientific Pub Co Pte Ltd ; 2013
    In:  International Journal of Foundations of Computer Science Vol. 24, No. 07 ( 2013-11), p. 1067-1082
    Details
    In: International Journal of Foundations of Computer Science, World Scientific Pub Co Pte Ltd, Vol. 24, No. 07 ( 2013-11), p. 1067-1082
    Abstract: The edit-distance between two strings is the smallest number of operations required to transform one string into the other. The distance between languages L 1 and L 2 is the smallest edit-distance between string w i ∈ L i , i = 1, 2. We consider the problem of computing the edit-distance of a given regular language and a given context-free language. First, we present an algorithm that finds for the languages an optimal alignment, that is, a sequence of edit operations that transforms a string in one language to a string in the other. The length of the optimal alignment, in the worst case, is exponential in the size of the given grammar and finite automaton. Then, we investigate the problem of computing only the edit-distance of the languages without explicitly producing an optimal alignment. We design a polynomial time algorithm that calculates the edit-distance based on unary homomorphisms.
    Type of Medium: Online Resource
    ISSN: 0129-0541 , 1793-6373
    URL: Article
    DOI: 10.1142/S0129054113400315
    Language: English
    Publisher: World Scientific Pub Co Pte Ltd
    Publication Date: 2013
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...