Source author record

K. V. Krishna

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Formal Languages and Automata Theory math.RA Discrete Mathematics Logic in Computer Science math.CO

Catalog footprint

Research overview

13works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2024arXiv

Word-Representability of Graphs with respect to Split Recomposition

In this work, we show that the class of word-representable graphs is closed under split recomposition and determine the representation number of the graph obtained by recomposing two word-representable graphs. Accordingly, we show that the class of parity graphs is word-representable. Further, we obtain a characteristic property by which the recomposition of comparability graphs is a comparability graph. Consequently, we also establish the permutation-representation number (prn) of the resulting comparability graph. We also introduce a subclass of comparability graphs, called prn-irreducible graphs. We provide a criterion such that the split recomposition of two prn-irreducible graphs is a comparability graph and determine the prn of the resultant graph.

preprint2016arXiv

Axiomatization of if-then-else over possibly non-halting programs and tests

In order to study the axiomatization of the if-then-else construct over possibly non-halting programs and tests, this paper introduces the notion of $C$ -sets by considering the tests from an abstract $C$ -algebra. When the $C$ -algebra is an ada, the axiomatization is shown to be complete by obtaining a subdirect representation of $C$ -sets. Further, this paper considers the equality test with the if-then-else construct and gives a complete axiomatization through the notion of agreeable $C$ -sets.

preprint2015arXiv

Radicals and Ideals of Affine Near-semirings over Brandt Semigroups

This work obtains all the right ideals, radicals, congruences and ideals of the affine near-semirings over Brandt semigroups.

preprint2015arXiv

Syntactic semigroup problem for the semigroup reducts of Affine Near-semirings over Brandt Semigroups

The syntactic semigroup problem is to decide whether a given finite semigroup is syntactic or not. This work investigates the syntactic semigroup problem for both the semigroup reducts of $A^+(B_n)$ , the affine near-semiring over a Brandt semigroup $B_n$ . It is ascertained that both the semigroup reducts of $A^+(B_n)$ are syntactic semigroups.

preprint2014arXiv

$L$ -Primitive Words in Submonoids

This work considers a natural generalization of primitivity with respect to a language. Given a language $L$ , a nonempty word $w$ is said to be $L$ -primitive if $w$ is not a proper power of any word in $L$ . After ascertaining the number of primitive words in submonoids of a free monoid, the work proceeds to count $L$ -primitive words in submonoids of a free monoid. The work also studies the distribution of $L$ -primitive words in certain subsets of free monoids.

preprint2014arXiv

Rank Properties of Multiplicative Semigroup Reduct of Affine Near-Semirings over $B_n$

This work investigates the rank properties of $A^+(B_n)$ , the multiplicative semigroup reduct of the affine near-semirings over an aperiodic Brandt semigroup $B_n$ . In this connection, the work obtains the small rank, lower rank and large rank of $A^+(B_n)$ . Further, the work provides lower bounds for intermediate rank and upper rank of $A^+(B_n)$ .

preprint2014arXiv

The Large Rank of a Finite Semigroup using Prime Subsets

The \emph{large rank} of a finite semigroup $Γ$ , denoted by $r_5(Γ)$ , is the least number $n$ such that every subset of $Γ$ with $n$ elements generates $Γ$ . Howie and Ribeiro showed that $r_5(Γ) = |V| + 1$ , where $V$ is a largest proper subsemigroup of $Γ$ . This work considers the complementary concept of subsemigroups, called \emph{prime subsets}, and gives an alternative approach to find the large rank of a finite semigroup. In this connection, the paper provides a shorter proof of Howie and Ribeiro's result about the large rank of Brandt semigroups. Further, this work obtains the large rank of the semigroup of order-preserving singular selfmaps.

preprint2013arXiv

Affine Near-Semirings over Brandt Semigroups

In order to study the structure of $A^+(B_n)$ -- the affine near-semiring over a Brandt semigroup -- this work completely characterizes the Green's classes of its semigroup reducts. In this connection, this work characterizes the elements of $A^+(B_n)$ and reports the size of $A^+(B_n)$ . Further, idempotents and regular elements of the semigroup reducts of $A^+(B_n)$ have also been characterized and studied some relevant semigroups in $A^+(B_n)$ .

preprint2013arXiv

Syntactic Complexity of Circular Semi-Flower Automata

We investigate the syntactic complexity of certain types of finitely generated submonoids of a free monoid. In fact, we consider those submonoids which are accepted by circular semi-flower automata (CSFA). Here, we show that the syntactic complexity of CSFA with at most one `branch point going in' (bpi) is linear. Further, we prove that the syntactic complexity of $n$ -state CSFA with two bpis over a binary alphabet is $2n(n+1)$ .

preprint2013arXiv

The Holonomy Decomposition of Circular Semi-Flower Automata

Eilenberg's holonomy decomposition is useful to ascertain the structural properties of automata. Using this method, Egri-Nagy and Nehaniv characterized the absence of certain types of cycles in automata. In the direction of studying the structure of automata with cycles, this work focuses on a special class of semi-flower automata and establish the holonomy decompositions of certain circular semi-flower automata.

preprint2013arXiv

The Ranks of the Additive Semigroup Reduct of Affine Near-Semiring over Brandt Semigroup

This work investigates the rank properties of $A^+(B_n)$ , the additive semigroup reduct of affine near-semiring over Brandt semigroup $B_n$ . In this connection, this work reports the ranks $r_1$ , $r_2$ , $r_3$ and $r_5$ of $A^+(B_n)$ and identifies a lower bound for the upper rank $r_4(A^+(B_n))$ . While this lower bound is found to be the $r_4(A^+(B_n))$ for $n \ge 6$ , in other cases where $2 \le n \le 5$ , the upper rank of $A^+(B_n)$ is still open for investigation.

preprint2012arXiv

A Sufficient Condition for Hanna Neumann Property of Submonoids of a Free Monoid

Using automata-theoretic approach, Giambruno and Restivo have investigated on the intersection of two finitely generated submonoids of the free monoid over a finite alphabet. In particular, they have obtained Hanna Neumann property for a special class of submonoids generated by finite prefix sets. This work continues their work and provides a sufficient condition for Hanna Neumann property for the entire class of submonoids generated by finite prefix sets. In this connection, a general rank formula for the submonoids which are accepted by semi-flower automata is also obtained.

preprint2011arXiv

The Rank and Hanna Neumann Property of Some Submonoids of a Free Monoid

This work aims at further investigations on the work of Giambruno and Restivo to find the rank of the intersection of two finitely generated submonoids of a free monoid. In this connection, we obtain the rank of a finitely generated submonoid of a free monoid that is accepted by semi-flower automaton with two bpi's. Further, when the product automaton of two deterministic semi-flower automata with a unique bpi is semi-flower with two bpi's, we obtain a sufficient condition on the product automaton in order to satisfy the Hanna Neumann property.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

K. V. Krishna

Research overview

Is this your work?

13 publications

Word-Representability of Graphs with respect to Split Recomposition

Axiomatization of if-then-else over possibly non-halting programs and tests

Radicals and Ideals of Affine Near-semirings over Brandt Semigroups

Syntactic semigroup problem for the semigroup reducts of Affine Near-semirings over Brandt Semigroups

$L$ -Primitive Words in Submonoids

Rank Properties of Multiplicative Semigroup Reduct of Affine Near-Semirings over $B_n$

The Large Rank of a Finite Semigroup using Prime Subsets

Affine Near-Semirings over Brandt Semigroups

Syntactic Complexity of Circular Semi-Flower Automata

The Holonomy Decomposition of Circular Semi-Flower Automata

The Ranks of the Additive Semigroup Reduct of Affine Near-Semiring over Brandt Semigroup

A Sufficient Condition for Hanna Neumann Property of Submonoids of a Free Monoid

The Rank and Hanna Neumann Property of Some Submonoids of a Free Monoid

See the researcher in context

Building this map preview

K. V. Krishna

Research overview

Is this your work?

13 publications

Word-Representability of Graphs with respect to Split Recomposition

Axiomatization of if-then-else over possibly non-halting programs and tests

Radicals and Ideals of Affine Near-semirings over Brandt Semigroups

Syntactic semigroup problem for the semigroup reducts of Affine Near-semirings over Brandt Semigroups

LLL-Primitive Words in Submonoids

Rank Properties of Multiplicative Semigroup Reduct of Affine Near-Semirings over BnB_nBn​

The Large Rank of a Finite Semigroup using Prime Subsets

Affine Near-Semirings over Brandt Semigroups

Syntactic Complexity of Circular Semi-Flower Automata

The Holonomy Decomposition of Circular Semi-Flower Automata

The Ranks of the Additive Semigroup Reduct of Affine Near-Semiring over Brandt Semigroup

A Sufficient Condition for Hanna Neumann Property of Submonoids of a Free Monoid

The Rank and Hanna Neumann Property of Some Submonoids of a Free Monoid

See the researcher in context

Building this map preview

$L$ -Primitive Words in Submonoids

Rank Properties of Multiplicative Semigroup Reduct of Affine Near-Semirings over $B_n$