Author name cluster

Yo-Sub Han

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

36 papers

2 author rows

TCS Journal 2026 Journal Article

A weak inverse of language neighborhoods and its properties

Hyunjoon Cheon
Yo-Sub Han

• Introduces the edit distance interior, a new inverse-like operation to the edit distance neighborhood. • Characterizes a hierarchy of interior languages, and their closure and decision properties. • Proves regular languages are closed under the operation, but context-free languages are not. While the edit distance neighborhood is useful for approximate pattern matching, it is not suitable for the negative lookahead feature for the practical regex matching engines. This motivates us to introduce a new operation. We define the edit distance interior operation on a language L, which is to compute the largest subset I ( L ) of L such that the edit distance neighborhood of I ( L ) is in L. In other words, L includes the edit distance neighborhood of the largest edit distance interior language. Given an edit distance value r, we show that the radius- r edit distance interior operation is a weak inverse of the radius- r edit distance neighborhood operation, and vice versa. A characterization of the edit distance interior languages and their proper hierarchy with respect to the radius are presented. Closure properties up to basic Boolean operations and decision properties of such languages are also discussed. In addition, we demonstrate that the regular languages are closed under the edit distance interior operation whereas the context-free languages are not.

AAAI Conference 2026 Conference Paper

WaterMod: Modular Token-Rank Partitioning for Probability-Balanced LLM Watermarking

Shinwoo Park
Hyejin Park
Hyeseon Ahn
Yo-Sub Han

Large language models now draft news, legal analyses, and software code with human-level fluency. At the same time, regulations such as the EU AI Act mandate that each synthetic passage carry an imperceptible, machine-verifiable mark for provenance. Conventional logit-based watermarks satisfy this requirement by selecting a pseudorandom green vocabulary at every decoding step and boosting its logits, yet the random split can exclude the highest-probability token and thus erode fluency. WaterMod mitigates this limitation through a probability-aware modular rule. The vocabulary is first sorted in descending model probability; the resulting ranks are then partitioned by the residue rank mod k, which distributes adjacent—and therefore semantically similar—tokens across different classes. A fixed bias of small magnitude is applied to one selected class. In the zero-bit setting (k=2), an entropy-adaptive gate selects either the even or the odd parity as the green list. Because the top two ranks fall into different parities, this choice embeds a detectable signal while guaranteeing that at least one high-probability token remains available for sampling. In the multi-bit regime (k>2), the current payload digit d selects the color class whose ranks satisfy rank mod k = d. Biasing the logits of that class embeds exactly one base-k digit—equivalently log2(k) bits—per decoding step, thereby enabling fine-grained provenance tracing. The same modular arithmetic therefore supports both binary attribution and rich payloads. Experimental results demonstrate that WaterMod consistently attains strong watermark detection performance while maintaining generation quality in both zero-bit and multi-bit settings. This robustness holds across a range of tasks, including natural language generation, mathematical reasoning, and code synthesis.

PDF Details DOI

EAAI Journal 2025 Journal Article

Advanced code time complexity prediction approach using contrastive learning

Shinwoo Park
Joonghyuk Hahn
Elizabeth Orwig
Sang-Ki Ko
Yo-Sub Han

It is a crucial task to predict the algorithmic time complexity for estimating the efficiency of a software code. Since the problem is known to be undecidable in theory, there is no 100% accurate tools to solve the problem. Even humans often make mistakes when analyzing the time complexity of code, and this process requires considerable effort and time to thoroughly examine the code. Therefore, we aim to develop an automated method for analyzing code time complexity. We observe that solution codes submitted for coding problems in competitive programming contests tend to have similar time complexities due to constraints such as time limits and functional requirements of the problems. Based on this observation, we propose a contrastive learning-based training strategy that aligns solution codes for the same competitive programming problem. Our training strategy clusters codes with similar time complexities by using both natural language problem descriptions and a single reference code per problem as anchors. This design enables the model to capture core algorithmic features such as loops and recursion more accurately. Experiments in three scenarios – in-dataset, cross-dataset, and cross-language – demonstrate substantial gains on pre-trained code models, consistently surpassing existing methods in both accuracy and generalizability. Our proposed training strategy yields an average 12. 54% improvement over cross-entropy-based training, and an 8. 01% improvement over data augmentation-based contrastive learning.

TCS Journal 2025 Journal Article

Approximate Cartesian tree pattern matching

Sungmin Kim
Yo-Sub Han

The Cartesian tree of a string is a binary tree, which is useful in capturing minimalities within strings. We study the approximate pattern matching problem for two Cartesian trees of two strings. We design a polynomial-time algorithm that computes the minimum edit cost when a given string is edited to match the Cartesian tree of the other string. We also design a linear-time algorithm that computes the (max, min)-convolution between two sorted arrays, which we use to speed up the algorithm computing the edit cost. Then, we adapt the algorithm that computes the edit cost to the approximate pattern matching problem, where we find all substrings of a given text that match a given Cartesian tree pattern within a given number of edit operations. We also consider variant problems such as the approximate Cartesian matching under Hamming distance, and present polynomial-time algorithms for the considered problems.

EAAI Journal 2025 Journal Article

Detecting code paraphrased by large language models using coding style features

Shinwoo Park
Hyundong Jin
Jeong-Won Cha
Yo-Sub Han

Recent progress in large language models (LLMs) for code generation has raised serious concerns about intellectual property protection. Malicious users can exploit LLMs to produce paraphrased versions of proprietary code that closely resemble the original. While the potential for LLM-assisted code paraphrasing continues to grow, research on detecting it remains limited, underscoring an urgent need for a detection system. We respond to this need by proposing two tasks. The first task is to detect whether code generated by an LLM is a paraphrased version of original human-written code. The second task is to identify which LLM is used to paraphrase the original code. For these tasks, we construct a dataset consisting of pairs of human-written code and LLM-paraphrased code using various LLMs. We statistically confirm significant differences in the coding styles of human-written and LLM-paraphrased code, particularly in terms of naming consistency, code structure, and readability. Based on these findings, we develop a detection method that identifies paraphrase relationships between human-written and LLM-generated code, and discover which LLM is used for the paraphrasing. Our detection method outperforms the best baselines in two tasks, improving F1 scores by 2. 64% and 15. 17% while achieving speedups of 1, 343x and 213x, respectively.

I&C Journal 2025 Journal Article

Existential and universal width of alternating finite automata

Yo-Sub Han
Sungmin Kim
Sang-Ki Ko
Kai Salomaa

The existential width of an alternating finite automaton (AFA) A on a string w is, roughly speaking, the number of nondeterministic choices that A uses in an accepting computation on w that uses least nondeterminism. The universal width of A on string w is the least number of parallel branches an accepting computation of A on w needs to have. The existential or universal width of A is said to be finite if it is bounded for all accepted strings. We show that finiteness of existential and universal width of an AFA is decidable and at least PSPACE-hard. We consider the problem of deciding whether the existential or universal width is bounded by a given integer. We show that the problem is PSPACE-complete for AFAs where the number of transitions defined for a given universal state and input symbol is bounded by a constant.

IJCAI Conference 2025 Conference Paper

LogiCase: Effective Test Case Generation from Logical Description in Competitive Programming

Sicheol Sung
Aditi
Dogyu Kim
Yo-Sub Han
Sang-Ki Ko

Automated Test Case Generation (ATCG) is crucial for evaluating software reliability, particularly in competitive programming where robust algorithm assessments depend on diverse and accurate test cases. However, existing ATCG methods often fail to meet complex specifications or generate effective corner cases, limiting their utility. In this work, we introduce Context-Free Grammars with Counters (CCFGs), a formalism that captures both syntactic and semantic structures in input specifications. Using a fine-tuned CodeT5 model, we translate natural language input specifications into CCFGs, enabling the systematic generation of high-quality test cases. Experiments on the CodeContests dataset demonstrate that CCFG-based test cases outperform baseline methods in identifying incorrect algorithms, achieving significant gains in validity and effectiveness. Our approach provides a scalable and reliable grammar-driven framework for enhancing automated competitive programming evaluations.

PDF Details DOI

TCS Journal 2024 Journal Article

Simon's congruence pattern matching

Sungmin Kim
Sang-Ki Ko
Yo-Sub Han

The Simon's congruence problem is to determine whether or not two strings have the same set of subsequences of length no greater than a given integer, and the problem can be answered in linear time. We consider the Simon's congruence pattern matching problem that looks for all substrings of a text that are congruent to a pattern under the Simon's congruence. We propose a linear time algorithm by reusing results from previous computations with the help of new data structures called X-trees and Y-trees. Moreover, we investigate several variants of the problem such as identifying the shortest substring or subsequence of the text that is congruent to the pattern under the Simon's congruence, or finding frequent matchings. We design efficient algorithms for these problems. We conclude the paper with two open problems: finding the longest congruent subsequence and optimizing the pattern matching problem.

TCS Journal 2023 Journal Article

Deciding path size of nondeterministic (and input-driven) pushdown automata

Yo-Sub Han
Sang-Ki Ko
Kai Salomaa

The degree of ambiguity (respectively, the path size) of a nondeterministic automaton, on a given input, measures the number of accepting computations (respectively, the number of all computations). It is known that deciding the finiteness of the degree of ambiguity of a nondeterministic pushdown automaton is undecidable. Also, it is undecidable for a given k ≥ 3 to decide whether the path size of a nondeterministic pushdown automaton is bounded by k. As the main result, we show that deciding the finiteness of the path size of a nondeterministic pushdown automaton can be done in polynomial time. Also, we show that the k-path problem for nondeterministic input-driven pushdown automata (respectively, for nondeterministic finite automata) is complete for exponential time (respectively, complete for polynomial space).

TCS Journal 2023 Journal Article

On Simon's congruence closure of a string

Sungmin Kim
Yo-Sub Han
Sang-Ki Ko
Kai Salomaa

Two strings are Simon's ∼ k -congruent if they have the same set of subsequences of length at most k. We study Simon's congruence closure of a string, which is regular by definition. Given a string w over an alphabet Σ, we present two efficient DFA constructions that accept all ∼ k -congruent strings with respect to w. We also present lower bounds for the state complexity of Simon's congruence closure. Then, we design a polynomial-time algorithm that answers the following open problem: “given a string w over a fixed-sized alphabet, an integer k and a (regular or context-free) language L, decide whether or not there exists a string v ∈ L such that w ∼ k v. ” In addition, for a variable-sized alphabet, we prove that the problem is NP-complete.

AAAI Conference 2022 Conference Paper

ALP: Data Augmentation Using Lexicalized PCFGs for Few-Shot Text Classification

Hazel H. Kim
Daecheol Woo
Seong Joon Oh
Jeong-Won Cha
Yo-Sub Han

Data augmentation has been an important ingredient for boosting performances of learned models. Prior data augmentation methods for few-shot text classification have led to great performance boosts. However, they have not been designed to capture the intricate compositional structure of natural language. As a result, they fail to generate samples with plausible and diverse sentence structures. Motivated by this, we present the data Augmentation using Lexicalized Probabilistic context-free grammars (ALP) that generates augmented samples with diverse syntactic structures with plausible grammar. The lexicalized PCFG parse trees consider both the constituents and dependencies to produce a syntactic frame that maximizes a variety of word choices in a syntactically preservable manner without specific domain experts. Experiments on few-shot text classification tasks demonstrate that ALP enhances many state-of-the-art classification methods. As a second contribution, we delve into the train-val splitting methodologies when a data augmentation method comes into play. We argue empirically that the traditional splitting of training and validation sets is sub-optimal compared to our novel augmentation-based splitting strategies that further expand the training split with the same number of labeled data. Taken together, our contributions on the data augmentation strategies yield a strong training recipe for few-shot text classification tasks.

TCS Journal 2021 Journal Article

A general architecture of oritatami systems for simulating arbitrary finite automata

Yo-Sub Han
Hwee Kim
Yusei Masuda
Shinnosuke Seki

In this paper, we propose an architecture of oritatami systems, a mathematical model of RNA cotranscriptional folding, with which one can simulate an arbitrary nondeterministic finite automaton (NFA) in a unified manner. The oritatami system is known to be Turing-universal but the simulation available so far requires 542 bead types and O ( t 4 log 2 ⁡ t ) steps in order to simulate t steps of a Turing machine. The architecture we propose employs only 337 bead types and requires just O ( t | Q | 4 | Σ | 2 ) steps to simulate an NFA with a state set Q working on a word of length t over an alphabet Σ.

TCS Journal 2021 Journal Article

Closest substring problems for regular languages

Yo-Sub Han
Sang-Ki Ko
Timothy Ng
Kai Salomaa

The Closest Substring problem asks whether there exists a consensus string w of given length ℓ such that each string in a set of strings L has a substring whose edit distance is at most r (called the radius) from w. The Closest Substring problem has been studied for finite sets of strings and is known to be NP-hard. We show that the Closest Substring problem for regular languages represented by nondeterministic finite automata (NFA) is PSPACE-complete. The problem remains PSPACE-hard even when the input is a deterministic finite automaton and the length ℓ and radius r are given in unary. Also we show that the Closest Substring problem for acyclic NFAs lies in the second level of the polynomial-time hierarchy and is both NP-hard and coNP-hard.

I&C Journal 2021 Journal Article

Consensus string problem for multiple regular languages

Yo-Sub Han
Sang-Ki Ko
Timothy Ng
Kai Salomaa

The consensus string (or centre string, closest string) of a set S of strings is defined as a string which is within a radius r from all strings in S. We study the consensus string problem for multiple languages recognized by finite automata (FAs). We define the consensus string of languages to be within distance at most r to some string in each of the languages. We also study the decidability and computational complexity of the consensus string problem for multiple formal language instances. We show that the consensus string problem for multiple regular languages is PSPACE -complete even when the radius r is fixed. We prove that the problem can be solved in polynomial time when the number of languages is fixed. Finally, we study that the consensus string problem for the class of input-driven languages and show that the problem is decidable.

AAAI Conference 2021 Conference Paper

SALNet: Semi-supervised Few-Shot Text Classification with Attention-based Lexicon Construction

Ju-Hyoung Lee
Sang-Ki Ko
Yo-Sub Han

We propose a semi-supervised bootstrap learning framework for few-shot text classification. From a small number of the initial data, our framework obtains a larger set of reliable training data by using the attention weights from an LSTMbased trained classifier. We first train an LSTM-based text classifier from a given labeled dataset using the attention mechanism. Then, we collect a set of words for each class called a lexicon, which is supposed to be a representative set of words for each class based on the attention weights calculated for the classification task. We bootstrap the classifier using the new data that are labeled by the combination of the classifier and the constructed lexicons to improve the prediction accuracy. As a result, our approach outperforms the previous state-of-the-art methods including semisupervised learning algorithms and pretraining algorithms for few-shot text classification task on four publicly available benchmark datasets. Moreover, we empirically confirm that the constructed lexicons are reliable enough and substantially improve the performance of the original classifier.

TCS Journal 2019 Journal Article

Alignment distance of regular tree languages

Yo-Sub Han
Sang-Ki Ko

We consider the tree alignment distance problem between a tree and a regular tree language. The tree alignment distance is an alternative of the tree edit-distance, in which we construct an optimal alignment between two trees and compute its cost instead of directly computing the minimum-cost of tree edits. The alignment distance is crucial for understanding the structural similarity between trees. We, in particular, consider the following problem: given a tree t and a tree automaton recognizing a regular tree language L, find the most similar tree from L with respect to t under the tree alignment metric. Regular tree languages are commonly used in practice such as XML schema or bioinformatics. We propose an O ( m n ) time algorithm for computing the (ordered) alignment distance between t and L when the maximum degree of t and trees in L is bounded by a constant, and O ( m n 2 ) time algorithm when the maximum degree of trees in L is not bounded, where m is the size of t and n is the size of a finite tree automaton for L. We also study the case where a tree is not necessarily ordered, and show that the time complexity remains O ( m n ) if the maximum degree is bounded and MAX SNP-hard otherwise.

TCS Journal 2019 Journal Article

Bound-decreasing duplication system

Da-Jung Cho
Yo-Sub Han
Hwee Kim

We introduce the bound-decreasing duplication operation, a new variant of tandem duplication operation, that has restrictions on the position and the maximum size of the duplication segment in a target string. Then, we examine the bound-decreasing duplication system that iteratively generates strings from an initial string using the bound-decreasing duplication operation. We show that there exists a nondeterministic finite-state automaton (NFA) accepting all strings generated by the bound-decreasing duplication system when an initial input is a single string; in other words, the bound-decreasing duplication system produces a regular language. This helps us to calculate the system capacity based on the corresponding NFA. Furthermore, we revisit a deduplication operation—a reverse process of duplication—on an NFA that transforms a given NFA to a smaller NFA while generating the same language by the string duplication system.

TCS Journal 2019 Journal Article

Ruleset optimization on isomorphic oritatami systems

Yo-Sub Han
Hwee Kim

We study an optimization problem of a computational folding model, proving its hardness and proposing heuristic algorithms. RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized out of a gene. An oritatami model (OM) is a computational model of this phenomenon that lets its sequence of beads (abstract molecules) fold cotranscriptionally by the interactions between beads, according to its ruleset. We study the problem of reducing the ruleset size, while keeping the terminal conformations geometrically the same. We first prove the hardness of finding the smallest ruleset, and then suggest two approaches that reduce the ruleset size efficiently.

TCS Journal 2019 Journal Article

Site-directed insertion: Language equations and decision problems

Da-Jung Cho
Yo-Sub Han
Kai Salomaa
Taylor J. Smith

Site-directed insertion is an overlapping insertion operation that can be viewed as analogous to the overlap assembly or chop operations that concatenate strings by overlapping a suffix and a prefix of the argument strings. We consider decision problems and language equations involving site-directed insertion. By relying on the tools provided by semantic shuffle on trajectories (M. Domaratzki, Developments in Language Theory 2004) we show that one variable equations involving site-directed insertion and regular constants can be solved algorithmically. We consider also maximal and minimal variants of the site-directed insertion operation and the nondeterministic state complexity of site-directed insertion.

TCS Journal 2017 Journal Article

Outfix-guided insertion

Da-Jung Cho
Yo-Sub Han
Timothy Ng
Kai Salomaa

Motivated by work on bio-operations on DNA strings, we consider an outfix-guided insertion operation that can be viewed as a generalization of the overlap assembly operation on strings studied previously. As the main result we construct a finite language L such that the outfix-guided insertion closure of L is non-regular. We consider also the closure properties of regular and (deterministic) context-free languages under the outfix-guided insertion operation and decision problems related to outfix-guided insertion. Deciding whether a language recognized by a deterministic finite automaton is closed under outfix-guided insertion can be done in polynomial time. The complexity of the corresponding question for nondeterministic finite automata remains open.

TCS Journal 2017 Journal Article

Pseudoknot-generating operation

Da-Jung Cho
Yo-Sub Han
Timothy Ng
Kai Salomaa

A pseudoknot is a crucial intra-molecular structure formed primarily in RNA strands and closely related to important biological processes. This motivates us to define an operation that generates all pseudoknots from a given sequence and consider algorithmic and language theoretic properties of the operation. We design an efficient algorithm that decides whether or not a given string is a pseudoknot of a regular language L. Our algorithm runs in linear time if L is given by a deterministic finite automaton. We study closure and decision properties of the pseudoknot-generating operation. For DNA encoding applications, pseudoknot structures are undesirable. We give polynomial-time algorithms that check whether or not a regular language L contains a pseudoknot or a pseudoknot generated by some string of L. Furthermore, we show that the corresponding questions for context-free languages are undecidable.

TCS Journal 2017 Journal Article

State complexity of permutation on finite languages over a binary alphabet

Da-Jung Cho
Daniel Goč
Yo-Sub Han
Sang-Ki Ko
Alexandros Palioudakis
Kai Salomaa

The set of all strings Parikh equivalent to a string in a language L is called the permutation of L. The permutation of a finite n-state DFA (deterministic finite automaton) language over a binary alphabet can be recognized by a DFA with n 2 − n + 2 2 states. We show that if the language consists of equal length binary strings the bound can be improved to f ( n ) = n 2 + n + 1 3 and for every n congruent to 1 modulo 3 there exists an n-state DFA A recognizing a set of equal length strings such that the minimal DFA for the permutation of L ( A ) needs f ( n ) states.

I&C Journal 2016 Journal Article

Approximate matching between a context-free grammar and a finite-state automaton

Sang-Ki Ko
Yo-Sub Han
Kai Salomaa

For a given context-free grammar (CFG) and a finite-state automaton (FA), we tackle the edit-distance problem—the problem of computing the most similar pair of strings in the two respective languages. In particular, we consider three different gap cost models for the edit-distance that are crucial for finding a proper alignment between two bio sequences: the linear, affine and concave models. We design efficient algorithms for the edit-distance between a CFG and an FA under these gap cost models. The time complexity of our algorithm for computing the linear or affine gap distance is polynomial and the time complexity for the concave gap distance is exponential.

TCS Journal 2016 Journal Article

State complexity of inversion operations

Da-Jung Cho
Yo-Sub Han
Sang-Ki Ko
Kai Salomaa

The reversal operation is well-studied in the literature and the deterministic (respectively, nondeterministic) state complexity of reversal is known to be 2 n (respectively, n). We consider the inversion operation where some substring of the given string is reversed. Formally, the inversion (respectively, prefix-inversion) of a language L consists of all strings u x R v such that u x v ∈ L (respectively, all strings u R x where u x ∈ L ). We show that the nondeterministic state complexity of prefix-inversion is Θ ( n 2 ) and that of inversion is Θ ( n 3 ). We show that the deterministic state complexity of prefix-inversion is at most 2 n ⋅ log ⁡ n + n and has lower bound 2 Ω ( n log ⁡ n ). The same lower bound holds for the state complexity of inversion, but for inversion we do not have a matching upper bound. We also study the state complexity of other variants of the inversion operation.

TCS Journal 2015 Journal Article

Alignment with non-overlapping inversions and translocations on two strings

Da-Jung Cho
Yo-Sub Han
Hwee Kim

An inversion and a translocation are important in bio sequence analysis and motivate researchers to consider the sequence alignment problem using these operations. Based on inversion and translocation, we introduce a new alignment problem with non-overlapping inversions and translocations—given two strings x and y, find an alignment with non-overlapping inversions and translocations for x and y. This problem has interesting application for finding a common sequence from two mutated sequences. We, in particular, consider the alignment problem when non-overlapping inversions and translocations are allowed for both x and y. We design an efficient algorithm that determines the existence of such an alignment and retrieves an alignment, if exists.

TCS Journal 2015 Journal Article

Non-overlapping inversion on strings and languages

Hwee Kim
Yo-Sub Han

Given a string, a non-overlapping inversion is to reverse some non-overlapping fragments of the string simultaneously. We define a non-overlapping inversion operation to be the computation of all possible non-overlapping inversions. We apply the operation on a string, which gives rise to a set of strings, and construct an NFA recognizing the set. Then, we design an efficient DFA reduction algorithm from the resulting NFA. We also consider the non-overlapping inversion operation on a language and show the closure properties for regular, context-free and context-sensitive languages. We furthermore examine iterative non-overlapping inversions and establish the closure properties. Finally, we introduce non-overlapping inversion-free languages and present the decidability results for regular and context-free languages.

TCS Journal 2014 Journal Article

Decidability of involution hypercodes

Da-Jung Cho
Yo-Sub Han
Sang-Ki Ko

Given a finite set X of strings, X is a hypercode if a string in X is not a subsequence of any other string in X. We consider hypercodes for involution codes, which are useful for DNA strand design, and define an involution hypercode. We then tackle the involution hypercode decidability problem; that is, to determine whether or not a given language is an involution hypercode. Based on the hypercode properties, we design a polynomial runtime algorithm for regular languages. We also prove that it is decidable whether or not a context-free language is an involution hypercode. Note that it is undecidable for some other involution codes such as involution prefix codes, suffix codes, and k-intercodes.

TCS Journal 2013 Journal Article

State complexity of combined operations for suffix-free regular languages

Hae-Sung Eom
Yo-Sub Han

We investigate the state complexity of combined operations for suffix-free regular languages. Suffix-free deterministic finite-state automata have a unique structural property that is crucial for obtaining the precise state complexity of basic operations. Based on the same property, we establish the state complexity of four combined operations: star-of-union, star-of-intersection, star-of-reversal and star-of-catenation. In the case of star-of-intersection, we only have an upper bound and the lower bound is open.

TCS Journal 2012 Journal Article

Analysis of a cellular automaton model for car traffic with a junction

Yo-Sub Han
Sang-Ki Ko

We propose a cellular automaton model that simulates traffic flow with a junction. We consider the form-one-lane rule and the merge-lane rule that decide which car moves ahead when two cars in two different lanes are in front of a junction. We simulate the proposed cellular automaton model for both rules, and generate fundamental diagrams and car distribution examples. Then, we analyze experimental results and demonstrate that the proposed model reflects the real world traffic flow with a junction according to the considered rules.

TCS Journal 2009 Journal Article

Nondeterministic state complexity of nested word automata

Yo-Sub Han
Kai Salomaa

We study the nondeterministic state complexity of Boolean operations on regular languages of nested words. For union and intersection we obtain matching upper and lower bounds. For complementation of a nondeterministic nested word automaton with n states we establish a lower bound Ω ( n! ) that is significantly worse than the exponential lower bound for ordinary nondeterministic finite automata (NFA). We develop techniques to prove lower bounds for the size of nondeterministic nested word automata that extend the known techniques used for NFAs.

TCS Journal 2009 Journal Article

State complexity of basic operations on suffix-free regular languages

Yo-Sub Han
Kai Salomaa

We investigate the state complexity of basic operations for suffix-free regular languages. The state complexity of an operation for regular languages is the number of states that are necessary and sufficient in the worst-case for the minimal deterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, Kleene star, reversal and the Boolean operations for suffix-free regular languages.

I&C Journal 2008 Journal Article

Generalizations of 1-deterministic regular languages

Yo-Sub Han
Derick Wood

We examine two generalizations of 1-deterministic regular languages that are used for the content models of DTDs in XML. They are k-lookahead determinism and k-block-determinism. The k-lookahead determinism uses the first k symbols w 1 w 2 ⋯ w k of the current input string as lookahead to process the first symbol w 1. On the other hand, the k-block-determinism takes k w 1 w 2 ⋯ w k as lookahead and process the whole k symbols. We show that there is a hierarchy in k-lookahead determinism and there is a proper hierarchy in k-block-determinism. Moreover, we prove that k-block-deterministic regular languages are a proper subfamily of deterministic k-lookahead regular languages.

TCS Journal 2007 Journal Article

Obtaining shorter regular expressions from finite-state automata

Yo-Sub Han
Derick Wood

We consider the use of state elimination to construct shorter regular expressions from finite-state automata (FAs). Although state elimination is an intuitive method for computing regular expressions from FAs, the resulting regular expressions are often very long and complicated. We examine the minimization of FAs to obtain shorter expressions first. Then, we introduce vertical chopping based on bridge states and horizontal chopping based on the structural properties of given FAs. We prove that we should not eliminate bridge states until we eliminate all non-bridge states to obtain shorter regular expressions. In addition, we suggest heuristics for state elimination that leads to shorter regular expressions based on vertical chopping and horizontal chopping.

TCS Journal 2007 Journal Article

On the existence of prime decompositions

Yo-Sub Han
Arto Salomaa
Kai Salomaa
Derick Wood
Sheng Yu

We investigate factorizations of regular languages in terms of prime languages. A language is said to be strongly prime decomposable if any way of factorizing it yields a prime decomposition in a finite number of steps. We give a characterization of the strongly prime decomposable regular languages and using the characterization we show that every regular language over a unary alphabet has a prime decomposition. We show that there exist non-regular unary languages that do not have prime decompositions. We also consider infinite factorizations of unary languages.

TCS Journal 2007 Journal Article

Prefix-free regular languages and pattern matching

Yo-Sub Han
Yajun Wang
Derick Wood

We explore the regular-expression matching problem with respect to prefix-freeness of the pattern. We prove that a prefix-free regular expression gives only a linear number of matching substrings in the size of a given text. Based on this observation, we propose an efficient algorithm for the prefix-free regular-expression matching problem. Furthermore, we suggest an algorithm to determine whether or not a given regular language is prefix-free.

MFCS Conference 2007 Conference Paper

State Complexity of Basic Operations on Suffix-Free Regular Languages

Yo-Sub Han
Kai Salomaa

Abstract We investigate the state complexity of basic operations for suffix-free regular languages. The state complexity of an operation for regular languages is the number of states that are necessary and sufficient in the worst-case for the minimal deterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, Kleene star, reversal and the Boolean operations for suffix-free regular languages.