BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Pascal Caron

Pascal Caron contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Formal Languages and Automata Theorymath.CO

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
2topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

6 published item(s)

preprint2022arXiv

State complexity of the star of a Boolean operation

Monsters and modifiers are two concepts recently developed in the state complexity theory. A monster is an automaton in which every function from states to states is represented by at least one letter. A modifier is a set of functions allowing one to transform a set of automata into one automaton. The paper describes a general strategy that can be used to compute the state complexity of many operations. We illustrate it on the problem of the star of a Boolean operation. After applying modifiers on monsters, the states of the resulting automata are assimilated to combinatorial objects: the tableaux. We investigate the combinatorics of these tableaux in order to deduce the state complexity. Specifically, we recover the state complexity of star of intersection and star of union, and we also give the exact state complexity of star of symmetrical difference. We thus harmonize the search strategy for the state complexity of star of any Boolean operations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Hierarchy of Block Deterministic Languages

A regular language is $k$-lookahead deterministic (resp. $k$-block deterministic) if it is specified by a $k$-lookahead deterministic (resp. $k$-block deterministic) regular expression. These two subclasses of regular languages have been respectively introduced by Han and Wood ($k$-lookahead determinism) and by Giammarresi et al. ($k$-block determinism) as a possible extension of one-unambiguous languages defined and characterized by Brüggemann-Klein and Wood. In this paper, we study the hierarchy and the inclusion links of these families. We first show that each $k$-block deterministic language is the alphabetic image of some one-unambiguous language. Moreover, we show that the conversion from a minimal DFA of a $k$-block deterministic regular language to a $k$-block deterministic automaton not only requires state elimination, and that the proof given by Han and Wood of a proper hierarchy in $k$-block deterministic languages based on this result is erroneous. Despite these results, we show by giving a parameterized family that there is a proper hierarchy in $k$-block deterministic regular languages. We also prove that there is a proper hierarchy in $k$-lookahead deterministic regular languages by studying particular properties of unary regular expressions. Finally, using our valid results, we confirm that the family of $k$-block deterministic regular languages is strictly included into the one of $k$-lookahead deterministic regular languages by showing that any $k$-block deterministic unary language is one-unambiguous.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

State complexity of catenation combined with a boolean operation: a unified approach

In this paper we study the state complexity of catenation combined with symmetric difference. First, an upper bound is computed using some combinatoric tools. Then, this bound is shown to be tight by giving a witness for it. Moreover, we relate this work with the study of state complexity for two other combinations: catenation with union and catenation with intersection. And we extract a unified approach which allows to obtain the state complexity of any combination involving catenation and a binary boolean operation.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Algorithms for Glushkov K-graphs

The automata arising from the well known conversion of regular expression to non deterministic automata have rather particular transition graphs. We refer to them as the Glushkov graphs, to honour his nice expression-to-automaton algorithmic short cut (On a synthesis algorithm for abstract automata, Ukr. Matem. Zhurnal, 12(2):147-156, 1960, In Russian). The Glushkov graphs have been characterized (P. Caron and D. Ziadi, Characterization of Glushkov automata. Theoret. Comput. Sci., 233(1-2):75-90, 2000) in terms of simple graph theoretical properties and certain reduction rules. We show how to carry, under certain restrictions, this characterization over to the weighted Glushkov graphs. With the weights in a semiring K, they are defined as the transition Glushkov K-graphs of the Weighted Finite Automata (WFA) obtained by the generalized Glushkov construction (P. Caron and M. Flouret, Glushkov construction for series: the non commutative case, Internat. J. Comput. Math., 80(4):457-472, 2003) from the K-expressions. It works provided that the semiring K is factorial and the K-expressions are in the so called star normal form (SNF) of Bruggeman-Klein (Regular expressions into finite automata, Theoret. Comput. Sci., 120(2):197-213, 1993) The restriction to the factorial semiring ensures to obtain algorithms. The restriction to the SNF would not be necessary if every K-expressions were equivalent to some with the same litteral length, as it is the case for the boolean semiring B but remains an open question for a general K.

0 citations0 reviewsNo code linkedOpen access