theory salon

vzn

19:56

another way of looking at that problem is as an inverse of a composition operation.

it seems relatively basic theory yet apparently as-yet unexplored.

Dave Lang

22:05

@vzn: I agree. Thanks for all your references and hints. I am going to think a bit more about the problem. If I cannot come to a conclusion I may post another more elementary question such as the one I mentioned in the chat.

vzn

22:33

@DaveLang sure. great to see at least 1 other person in universe looking at similar problems.

mused/wondered on the inverse-composition question ~ two decades ago. think its a worthwhile question for the tcs group. if you dont ask it, maybe I will.

Dave Lang

There are decompositions for k-valued transducers into unambiguous ones (special case of single-valued), e.g. by Weber "Decomposing a k-valued transducer into k unambiguous ones".

Feel free to ask the question. I am curious if anybody jumps on it. Meanwhile I think my first post was unnecessarily technical, thus hiding the essential question.

vzn

ok. do we agree on the "infinite word" distinction yet? am asking because am trying to get it right myself

Dave Lang

transducers accept finite input/output words

vzn

right. apparently SSTs work with infinite words? not too familiar with them

Dave Lang

generalized sequential machines seem to be sometimes defined on finite and sometimes on infinite words

vzn

22:40

ok. havent seen GSMs defined on infinite words. have seen them defined as working on finite words in hopcroft/ullman (an early ref. now ~3 decades old)

will go ahead & ask the question.

Dave Lang

I would have to look up a reference. I remember that someone even stated that GSMs are inconsistently used in literature but transducers operate definitely on finite words.

vzn

ok. that happens sometimes. was somwhat frustrated even yrs ago with all the separate defns of transducer-like automata. shows a lack of standardization in the area...

Dave Lang

SSTs seem to operate on finite words as well.

GSMs are sometimes also referred to as real-time transducers

The essential difference to transducers is that they must read an input symbol on each transition.

vzn

are you at a university?

Dave Lang

Hence, they cannot express epsilon-loops ("babbling automata")

no

vzn

22:47

what is your bkgd?

Dave Lang

cs, program analysis and transformation

vzn

(under)grad?

Dave Lang

grad

vzn

do you have cs undergrad degree?

Dave Lang

master

what about you?

vzn

22:52

BS software engr.

so you have a masters degree in CS?

Dave Lang

yes

vzn

did you do a thesis?

Dave Lang

but im not an automata expert

yes

vzn

there are not a huge number of automata experts in the world.

what was your thesis on?

[am typing question right now]

Dave Lang

on sublinear classification algorithms

has nothing to do with program analysis

i got interested in this topic afterwards

vzn

22:57

hm, what are sublinear classification algorithms? "program analysis & transformation" is rather vague

Dave Lang

classification: given a prioritized set of rules and a finite string, find the highest priority matching rule

program analysis: abstract interpretation

program transformation: mostly binary translation

vzn

0

Q: inverse of transducer compositions operation/algorithm

this is a question that occurred to me many yrs ago after delving into the area and is similar to one recently asked by DL[1] who recently independently raised it also. after some back-and-forth we agree it seems basic & yet not to have been studied. consider GSM or (nearly equivalently FSM tran...

Dave Lang

thanks for the posting.

vzn

sure.

program analysis/transformation defined: still rather vague!

Dave Lang

program analysis: classical value analysis, i.e. find an abstract value for each variable at each program point overapproximating the possible values it may assume at runtime

program transformation: mostly practical stuff, i.e. translating instruction set architectures

vzn

23:05

curious, where'd you go for grad/undergrad?

Dave Lang

in germany, saarland university

and you?

vzn

in united states.

state school.

"translating instruction set architectures" reminds me of jvm.

java virtual machine.

work(ed) a lot with java over the yrs.

Dave Lang

yes they do it as well dynamically

you can also do it statically

of course it is not deciable

vzn

yeah the dynamic optimization of the jvm is pretty cool. "hotspot"

pretty advanced.

Dave Lang

but for restricted programs it can be done

same holds for javascript engines

vzn

23:08

yeah I was just thinking that I heard that google was optimizing js with hotspot-like technology. maybe in V8 engine.

Dave Lang

they collaps certain paths in the call stack e.g.

vzn

have also been dinking with js quite a bit last few yrs

plz upvote the question. 1st impressions make a difference =D

Dave Lang

sorry, i forgot

vzn

the composition problem interests me as far as analyzing transducers which can also be closely tied to Turing machine sequential ID cascades.

in other words there are some seemingly somewhat natural Turing-complete questions relating to transducers.

arrived at it via studying the collatz conjecture.

Dave Lang

I read on your blog that you are interested in the topic

vzn

23:12

cool yeah thx for reading.

Dave Lang

With Turing-complete questions, do you mean undecidable questions?

vzn

yrs ago thought it could possibly crack collatz, now am more pessimistic but still think its worthwhile direction....

let me dig up another question that relates the two

Dave Lang

ok

vzn

0

Q: iterations of a $\epsilon$-FSM transducer on a tape as equivalent to a TM computation

A question partly inspired by a recent question[1] on the utility of FSMs: Years ago noticed the following property of FSM transducers with $\epsilon$-transitions (which allow an "empty" transition without an output symbol). Its not complicated but not trivial either; it seems to be rarely taught...

reference-request automata-theory turing-machines ho.history-overview

0 votes. the "community" was not impressed :|

re Weber, "Decomposing a k-valued transducer into k unambiguous ones"... did you look at that

Dave Lang

But you got some replies :)

I was just reading the paper when we started talking

vzn

23:17

hah yeah. it always annoys me a bit when people reply without upvoting. as the kids say whatever :p

Dave Lang

:)

vzn

hey, though, a reply by a luminary like shallit is cool. gotta take what one can get around here.

Dave Lang

Still the automata community here appears to be quite big

vzn

relatively speaking.

Dave Lang

It seems stackexchange largely took over the usenet.

sci.comp et al

vzn

23:21

this guy has answered at least 2 of my automata questions. has some interesting research, skimmed thru his slides once.

J.-E. Pin

1.3k 6 15

automata-theory fl.formal-languages regular-language dfa reference-request regular-expressions ds.algorithms

yes stackexchange is quite a wonder. pros, cons, pluses, minuses. warts & all.

tcs.se has a lot of users, but not really that much activity relative to users.

Dave Lang

informatik.uni-trier.de/~ley/pers/hd/p/Pin:Jean==Eacute=ric

i suppose

I'm curious how this question goes. In any case I am going to think further about it

A semi-decision procedure is clearly possible and one possible approach is the one mentioned in a recent Microsoft paper

vzn

fyi think that "who" asks tends to have a big effect around here...

re "semi-decision" procedure.. is that defined somewhere?

Dave Lang

semi-decision meaning that there is an algorithm that terminates if there is a positive answer to the question and otherwise diverges

vzn

yeah Ive been looking for a term for that.

all over the place.

Dave Lang

So by introducing a bound on the number of states in the unknown automaton X the problem becomes decidable

vzn

23:29

yeah. there seems to be a very interesting boundary of undecidable/decidable problems for transducers.

seems mostly unexplored, terra incognita.

the microsoft paper is interesting although it seems a little too abstract, and then its examples/applications seem a bit weak, eg HTMLdecode.

image blurring seemed more interesting.

Dave Lang

On the other hand the symbolic automata are very consise.

Plus they extend it to infinite automata by relying on decidable logics.

vzn

ok yeah I have been hearing about SFT-like objects in another paper. labelling transitions with formulas. seems to be a new trend.

saw it with grammars.

Dave Lang

There is renewed interest in program synthesis also

e.g. the famous sketch (programming with holes)

I think automata are a nice way to complement existing approaches

vzn

ok found the paper.

its an interesting contrast/juxtaposition.

An Inﬁnite Automaton Characterization of Double Exponential Time Salvatore La Torre, P. Madhusudan, and Gennaro Parlato

@DaveLang ?

have long been thinking that new automata types seem to lead to new research insights & the boundary between decidable/undecidable.

Dave Lang

I was just skimming the paper

vzn

23:36

feel sometimes that "automata space" has not been highly explored. still surprises in store

Dave Lang

My feeling for the decomposition question is that it depends on the type of automaton

For single- and maybe finite-valued automata I guess it should be decidable.

For general non-deterministic ones obviously not because equivalence is already undecidable (e.g. by reduction to PCP)

vzn

re hopcroft & ullman, it seemed many questions about automata with epsilon transitions led to undecidability, without them it is more manageable

yeah nondeterminism is a key question/"hinge"...

Dave Lang

yes, I think this is how GSMs might have appeared originally.

whether finite or infinite words is probably not so important

vzn

so how do you want to apply the transducer questions? do you have an application in mind

Dave Lang

Not a very specific one

vzn

23:42

ok

Dave Lang

In my original problem I think of the two to be synthesized automata X and Y to be the something like missing information to make A and B equal

vzn

my interest is in natural decompositions of a Turing-complete function. suspect there is something there...again unexplored...

Dave Lang

To arrive at a more succinct representation?

vzn

similar to the krohn-rhodes decomposition which fascinates me. suspect there is some similar decomposition for TM complete functions which might unlock a lot of insights.

yes minimization might be one natural application.

Dave Lang

I couldn't yet read about it

vzn

23:46

termination analysis is one of my main motivations.

automated theorem proving. etc.

Dave Lang

did you work with coq, hol or agda etc?

vzn

have not.

have gone in direction of a lot of "homegrown" techniques.

versus the collatz dragon/monster.

similar to/influenced by datamining...

Dave Lang

there is a nice paradigm called total functional programming

termination is guaranteed there

but it is still very powerful

vzn

hmm there are some related questions to that on tcs.

Dave Lang

coq employs this idea

vzn

23:49

people asking about more limited systems than TM complete that provably terminate...(as I recall)

yeah coq/thm proving is an occasional topic on both CS sites & there are many cool question on subj in archives.

Dave Lang

there is also quite some recent work about synthesis of ranking functions

to show termination

vzn

interesting

Dave Lang

another direction is to use curry howard isomorphism in form of dependent types

to establish properties of your program via its types

agda uses such an approach

im not an expert though on either of them

vzn

yeah the curry-howard correspondence seems underappreciated to me

slowly math/cs are getting married...

Dave Lang

yep :)

I am going to read a bit further now

vzn

23:55

possibly epitomized best so far by curry-howard...

ok

Dave Lang

We will stay in touch about the topic for sure

vzn

ok cool sure

Dave Lang

It was nice talking to you and again thanks for your support.

vzn

sure! nice talking 2u2

Transcript for